図面 (/)

技術 疑似乱数生成装置及び疑似乱数生成プログラム

出願人 三菱電機株式会社
発明者 内藤祐介反町亨粕谷智巳
出願日 2015年2月19日 (6年9ヶ月経過) 出願番号 2017-500219
公開日 2017年7月13日 (4年4ヶ月経過) 公開番号 WO2016-132506
状態 特許登録済
技術分野 暗号化・復号化装置及び秘密通信
主要キーワード サーキットリー 出力長 フィードフォワード演算 ラウンド関数 通信チップ 利用モード トランスミッター 不可能性
関連する未来課題
重要な関連分野

この項目の情報は公開日時点(2017年7月13日)のものです。
また、この項目は機械的に抽出しているため、正しく解析できていない場合があります

図面 (9)

課題・解決手段

疑似乱数生成装置は、i=1,...,nの各整数値iについて昇順に、値st[i−1]を入力として関数F[i]によりb[i]ビットの値st[i]を計算する。疑似乱数生成装置は、i=1,...,nの少なくとも一部の整数値iについて、値jを整数値iよりも小さい整数値として、値st[j]のうちの少なくとも一部のビットと、値st[i]のうちの少なくとも一部のビットとを入力として関数g[i]によりr[i]ビットの値x[i]を計算する。疑似乱数生成装置は、関数g[i]により計算された値x[i]を結合して、疑似乱数とする。

概要

背景

真の乱数は、全てのビットランダムに選ばれた値のことである。

バーナム暗号は真の乱数を用いた場合に解読不可能な暗号である。バーナム暗号は、平文mと、平文mと同じビット長の真の乱数rとの排他的論理和暗号文とする。バーナム暗号を用いて2者間で暗号通信を行う場合、平文と同じ長さの真の乱数を共有しておく必要がある。送りたい平文が長くなると共有する真の乱数も長くなる。

しかし、長い真の乱数を安全に配送することは困難である。そこで、真の乱数の代わりに疑似乱数が用いられている。
疑似乱数を用いる場合、暗号通信を行う2者間で固定長kビットの秘密鍵を共有しておき、秘密鍵と、疑似乱数生成毎に異なる値IVとを入力として疑似乱数生成関数により疑似乱数が生成される。

疑似乱数生成関数は、入力長と出力長とが固定の非線形関数と、非線形関数を用いて任意長の疑似乱数を生成する構造を規定した利用モードとからなる。

疑似乱数生成関数は、次の(1)(2)を証明できる関数のことである。
(1)非線形関数が理想的な非線形関数であると仮定したときに、疑似乱数生成関数が出力する値を、真の乱数と識別するための計算量が膨大であること。疑似乱数生成関数が出力する値を、真の乱数と識別するための計算量が2n必要な場合、疑似乱数生成関数はnビットの識別不可能性を持つという。
(2)非線形関数が理想的な非線形関数と異なるという性質を見つけるための計算量が膨大であること。これは、非線形関数に対して、差分攻撃法と線形攻撃法とが成功する計算量が膨大であることである。

非特許文献1には、Sponge構造を用いた利用モードについて記載されている。Sponge構造を用いた利用モードにおいて、非線形関数の入力値及び出力値がbビット、非線形関数から抽出される値がrビットであるとする。また、暗号通信を行う2者間で共有した秘密鍵はkビットである。非特許文献2には、Sponge構造を用いた利用モードは、非線形関数が理想的な関数である場合に、c=b−rとすると、min{c,b/2,k}ビットの乱数との識別不可能性を持つことが示されている。

概要

疑似乱数生成装置は、i=1,...,nの各整数値iについて昇順に、値st[i−1]を入力として関数F[i]によりb[i]ビットの値st[i]を計算する。疑似乱数生成装置は、i=1,...,nの少なくとも一部の整数値iについて、値jを整数値iよりも小さい整数値として、値st[j]のうちの少なくとも一部のビットと、値st[i]のうちの少なくとも一部のビットとを入力として関数g[i]によりr[i]ビットの値x[i]を計算する。疑似乱数生成装置は、関数g[i]により計算された値x[i]を結合して、疑似乱数とする。

目的

この発明は、識別不可能性の安全性を値cに依存しないようにすることを目的とする

効果

実績

技術文献被引用数
0件
牽制数
0件

この技術が所属する分野

ライセンス契約や譲渡などの可能性がある特許掲載中! 開放特許随時追加・更新中 詳しくはこちら

請求項1

関数F[0]により値st[0]を計算する第1関数F計算部と、値nを1以上の整数値として、i=1,...,nの各整数値iについて昇順に、値st[i−1]を入力として関数F[i]により値st[i]を計算する第2関数F計算部と、i=1,...,nの少なくとも一部の整数値iについて、値jを整数値iよりも小さい整数値として、値st[j]のうちの少なくとも一部のビットと、値st[i]のうちの少なくとも一部のビットとを入力として関数g[i]により値x[i]を計算する関数g計算部と、前記関数g計算部が計算した値x[i]から疑似乱数を計算する乱数値計算部とを備える疑似乱数生成装置

請求項2

前記関数g計算部は、i=1,...,nの各整数値iについて、値st[i−1]のうちの少なくとも一部のビットと、値st[i]のうちの少なくとも一部のビットとを入力として関数g[i]により値x[i]を計算する請求項1に記載の疑似乱数生成装置。

請求項3

i=1,...,nの各整数値iについての関数F[i]は同一の非線形関数である請求項1又は2に記載の疑似乱数生成装置。

請求項4

i=0,...,nの各整数値iについての関数F[i]は同一の非線形関数である請求項1又は2に記載の疑似乱数生成装置。

請求項5

前記関数F[0]は、ブロック暗号を構成するラウンド関数R[i]であって、値tを1以上の整数として、i=1,...,tの各整数値iについてのラウンド関数R[i]が順に計算される関数であり、i=1,...,nの各整数値iについての前記関数F[i]は、前記関数F[0]で計算されるラウンド関数R[i]のうちの少なくとも一部のラウンド関数R[i]が順に計算される関数である請求項1又は2に記載の疑似乱数生成装置。

請求項6

前記関数F[0]は、ブロック暗号を構成するラウンド関数R[i]であって、値tを1以上の整数として、i=1,...,tの各整数値iについてのラウンド関数R[i]が順に計算され、さらに、前記ラウンド関数R[i]のうちの少なくとも一部のラウンド関数R[i]が順に計算される関数であり、i=1,...,nの各整数値iについての前記関数F[i]は、前記関数F[0]で計算されるラウンド関数R[i]のうちの少なくとも一部のラウンド関数R[i]が順に計算される関数である請求項1又は2に記載の疑似乱数生成装置。

請求項7

前記第1関数F計算部は、前記関数F[0]で計算されるラウンド関数R[i]のうち少なくとも一部のラウンド関数R[i]により計算された値を結合して値st[0]を計算し、前記第2関数F計算部は、前記関数F[i]で計算されるラウンド関数R[i]のうち少なくとも一部のラウンド関数R[i]により計算された値を結合して値st[i]を計算する請求項5又は6に記載の疑似乱数生成装置。

請求項8

前記第2関数F計算部は、値st[i−1]のビットから選択された一部のビットを初めに計算されるラウンド関数R[i]の入力値とし、前記st[i−1]のビットから選択された一部のビットを各ラウンド関数R[i]で使用される鍵とする請求項5から7までのいずれか1項に記載の疑似乱数生成装置。

請求項9

前記ブロック暗号は、AES(AdvancedEncryptionStandard)であり、i=1,...,tの各整数値iについてのラウンド関数R[i]は、AESのラウンド関数である請求項5から8のいずれか1項に記載の疑似乱数生成装置。

請求項10

前記ブロック暗号は、Camellia(登録商標)であり、i=1,...,tの各整数値iについてのラウンド関数R[i]は、Camellia(登録商標)のラウンド関数である請求項5から8のいずれか1項に記載の疑似乱数生成装置。

請求項11

i=1,...,nの各整数値iについての前記関数g[i]は、前記値st[i−1]のうちの少なくとも一部のビットと、前記値st[i]のうちの少なくとも一部のビットとの排他的論理和をとり、少なくとも一部のビットを値x[i]として出力する関数である請求項2に記載の疑似乱数生成装置。

請求項12

i=1,...,nの各整数値iについての前記値st[i]は、同一ビット数である請求項11に記載の疑似乱数生成装置。

請求項13

関数F[0]により値st[0]を計算する第1関数F計算処理と、値nを1以上の整数として、i=1,...,nの各整数値iについて昇順に、値st[i−1]を入力として関数F[i]により値st[i]を計算する第2関数F計算処理と、i=1,...,nの少なくとも一部の整数値iについて、値jを整数値iよりも小さい整数として、値st[j]のうちの少なくとも一部のビットと、値st[i]のうちの少なくとも一部のビットとを入力として関数g[i]により値x[i]を計算する関数g計算処理と、前記関数g計算処理で計算した値x[i]から疑似乱数を計算する乱数値計算処理とをコンピュータに実行させる疑似乱数生成プログラム

技術分野

0001

この発明は、疑似乱数を生成する技術に関する。

背景技術

0002

真の乱数は、全てのビットランダムに選ばれた値のことである。

0003

バーナム暗号は真の乱数を用いた場合に解読不可能な暗号である。バーナム暗号は、平文mと、平文mと同じビット長の真の乱数rとの排他的論理和暗号文とする。バーナム暗号を用いて2者間で暗号通信を行う場合、平文と同じ長さの真の乱数を共有しておく必要がある。送りたい平文が長くなると共有する真の乱数も長くなる。

0004

しかし、長い真の乱数を安全に配送することは困難である。そこで、真の乱数の代わりに疑似乱数が用いられている。
疑似乱数を用いる場合、暗号通信を行う2者間で固定長kビットの秘密鍵を共有しておき、秘密鍵と、疑似乱数生成毎に異なる値IVとを入力として疑似乱数生成関数により疑似乱数が生成される。

0005

疑似乱数生成関数は、入力長と出力長とが固定の非線形関数と、非線形関数を用いて任意長の疑似乱数を生成する構造を規定した利用モードとからなる。

0006

疑似乱数生成関数は、次の(1)(2)を証明できる関数のことである。
(1)非線形関数が理想的な非線形関数であると仮定したときに、疑似乱数生成関数が出力する値を、真の乱数と識別するための計算量が膨大であること。疑似乱数生成関数が出力する値を、真の乱数と識別するための計算量が2n必要な場合、疑似乱数生成関数はnビットの識別不可能性を持つという。
(2)非線形関数が理想的な非線形関数と異なるという性質を見つけるための計算量が膨大であること。これは、非線形関数に対して、差分攻撃法と線形攻撃法とが成功する計算量が膨大であることである。

0007

非特許文献1には、Sponge構造を用いた利用モードについて記載されている。Sponge構造を用いた利用モードにおいて、非線形関数の入力値及び出力値がbビット、非線形関数から抽出される値がrビットであるとする。また、暗号通信を行う2者間で共有した秘密鍵はkビットである。非特許文献2には、Sponge構造を用いた利用モードは、非線形関数が理想的な関数である場合に、c=b−rとすると、min{c,b/2,k}ビットの乱数との識別不可能性を持つことが示されている。

先行技術

0008

Guido Bertoni, Joan Daemen, Michael Peeters and Gilles Van Assche.“Cryptographic sponge functions”.
Philipp Jovanovic, Atul Luykx, Bart Mennink.“Beyond 2^{c/2} Security in Sponge−Based Authenticated Encryption Modes” ASIACRYPT (1) 2014. p.85−104.
Federal Information Processing StandardsPublication 197. Specification for the ADVANCED ENCRYPTION STANDARD (AES)
青木和呂, 市川哲也, 神田雅透,井 充, 盛合志, 中嶋純子, 時田俊雄. 128ビットブロック暗号Camelliaアルゴリズム仕様書

発明が解決しようとする課題

0009

値cが小さくなると非線形関数から抽出されるビット長rが長くなる。ビット長rが長くなると、非線形関数を計算する回数を減らすことができ、疑似乱数を計算する計算量を減らすことができる。値cが0の場合が最も計算量を少なくなる。しかし、Sponge構造を用いた既存の利用モードでは、識別不可能性の安全性が値cに依存しており、値cを小さくすることが困難である。
この発明は、識別不可能性の安全性を値cに依存しないようにすることを目的とする。

課題を解決するための手段

0010

この発明に係る疑似乱数生成装置は、
関数F[0]により値st[0]を計算する第1関数F計算部と、
値nを1以上の整数値として、i=1,...,nの各整数値iについて昇順に、値st[i−1]を入力として関数F[i]により値st[i]を計算する第2関数F計算部と、
i=1,...,nの少なくとも一部の整数値iについて、値jを整数値iよりも小さい整数値として、値st[j]のうちの少なくとも一部のビットと、値st[i]のうちの少なくとも一部のビットとを入力として関数g[i]により値x[i]を計算する関数g計算部と、
前記関数g計算部が計算した値x[i]から疑似乱数を計算する乱数値計算部と
を備える。

発明の効果

0011

この発明では、関数F[i]により計算された値st[i]をそのまま利用せず、関数F[j]により計算された値st[j]を用いて値st[i]を変換した上で利用する。これにより、関数F[i]により計算された値st[i]を推定することが困難になり、識別不可能性の安全性を値cに依存しないようにすることができる。

図面の簡単な説明

0012

Sponge構造を用いた疑似乱数生成関数の構成図。
実施の形態1に係る疑似乱数生成関数の構成図。
実施の形態1に係る関数gの構成図。
実施の形態1に係る疑似乱数生成装置10の構成図。
実施の形態1に係る疑似乱数生成装置10の処理を示すフローチャート
実施の形態2に係る非線形関数Fの構成図。
実施の形態2に係る非線形関数Fの構成図。
実施の形態1,2に係る疑似乱数生成装置10のハードウェア構成図。

実施例

0013

実施の形態1.
***構成の説明***
図1に基づき、Sponge構造を用いた疑似乱数生成関数の構成を説明する。
Sponge構造を用いた疑似乱数生成関数では、入力値がbビットであり、出力値がbビットである理想的な非線形関数Pを用いる。
まず、関数cを用いて、値IVと秘密鍵Kとを結合し、さらに必要に応じて固定値padを結合してbビットとした値m[0]が生成される。値m[0]を入力として非線形関数Pにより値st[1]が計算される。値st[1]のうちrビットが疑似乱数に代入される。
次に、i=2,...,nの各整数値iについて昇順に、値st[i−1]を入力として非線形関数Pにより値st[i]が計算される。値st[i]のうちrビットが疑似乱数に結合される。これにより、疑似乱数が生成される。
値nは、必要な疑似乱数のビット長に応じて決定される。

0014

図2に基づき、実施の形態1に係る疑似乱数生成関数の構成を説明する。
まず、入力値IVと秘密鍵Kとを入力として非線形関数F[0]によりb[0]ビットの値st[0]が計算される。
次に、i=1,...,nの各整数値iについて昇順に、値st[i−1]を入力として関数F[i]によりb[i]ビットの値st[i]が計算される。そして、i=1,...,nの少なくとも一部の整数値iについて、値jを整数値iよりも小さい整数値として、値st[j]のうちの少なくとも一部のビットと、値st[i]のうちの少なくとも一部のビットとを入力として関数g[i]によりr[i]ビットの値x[i]が計算される。ここでは、i=1,...,nの各整数値iについて、値st[i−1]のうちの少なくとも一部のビットと、値st[i]のうちの少なくとも一部のビットとを入力として関数g[i]によりr[i]ビットの値x[i]が計算される。
関数g[i]により計算された値x[i]が結合され、疑似乱数となる。

0015

値nは、必要な疑似乱数のビット長に応じて決定される1以上の値である。

0016

図3に基づき、実施の形態1に係る関数gの構成について説明する。
i=1,...,nの各整数値iについての関数g[i]は、値st[i−1]のうちの少なくとも一部のビットと、値st[i]のうちの少なくとも一部のビットとの排他的論理和をとる。そして、関数g[i]は、排他的論理和の少なくとも一部のビットであるr[i]ビットを抽出して、値x[i]として出力する。

0017

なお、i=1,...,nの各整数値iについての非線形関数F[i]は、同一の非線形関数であってもよい。また、非線形関数F[0]もi=1,...,nの各整数値iについての非線形関数F[i]と同一の非線形関数であってもよい。つまり、i=0,...,nの各整数値iについての非線形関数F[i]は、同一の非線形関数であってもよい。もちろん、i=0,...,nの各整数値iについての非線形関数F[i]は、異なる関数であってもよい。

0018

また、i=1,...,nの各整数値iについての値st[i]は、同一のビット数であってもよい。つまり、i=1,...,nの各整数値iについてのビット数b[i]は、同一のbビットであってもよい。

0019

図4に基づき、実施の形態1に係る疑似乱数生成装置10の構成を説明する。
疑似乱数生成装置10は、図2に示す疑似乱数生成関数を計算して疑似乱数を生成する。疑似乱数生成装置10は、取得部11と、関数F計算部12と、関数g計算部13と、乱数値計算部14とを備える。

0020

取得部11は、値IV及び秘密鍵Kを取得する。値IVは、疑似乱数を生成する度に異なる値である。秘密鍵Kは、暗号通信の相手と予め共有された鍵である。なお、疑似乱数を暗号通信に用いない場合も考えられる。したがって、秘密鍵Kは、暗号通信の相手と予め共有された鍵ではなく、任意の値であってもよい。
値IVは、疑似乱数を生成する度に、疑似乱数生成装置10の利用者入力装置により入力し、取得部11は入力された値IVを取得してもよい。また、値IVは、疑似乱数生成装置10が備える記憶装置に記憶されており、取得部11は記憶された値IVを取得してもよい。同様に、秘密鍵Kは、疑似乱数を生成する度に、疑似乱数生成装置10の利用者が入力装置により入力し、取得部11は入力された秘密鍵Kを取得してもよい。また、秘密鍵Kは、疑似乱数生成装置10が備える記憶装置に記憶されており、取得部11は記憶された秘密鍵Kを取得してもよい。

0021

関数F計算部12は、非線形関数F[i]を計算する。関数F計算部12は、第1関数F計算部121と、第2関数F計算部122とを備える。
第1関数F計算部121は、取得部11が取得した値IV及び秘密鍵Kを入力として、関数F[0]により値st[0]を計算する。
第2関数F計算部122は、i=1,...,nの各整数値iについて昇順に、値st[i−1]を入力として関数F[i]により値st[i]を計算する。

0022

関数g計算部13は、関数g[i]を計算する。
関数g計算部13は、値jを整数値iよりも小さい整数値として、値st[j]のうちの少なくとも一部のビットと、値st[i]のうちの少なくとも一部のビットとを入力として関数g[i]によりr[i]ビットの値x[i]を計算する。ここでは、関数g計算部13は、i=1,...,nの各整数値iについて、値st[i−1]のうちの少なくとも一部のビットと、値st[i]のうちの少なくとも一部のビットとを入力として関数g[i]によりr[i]ビットの値x[i]を計算する。

0023

乱数値計算部14は、関数g計算部が計算した値x[i]から疑似乱数を計算する。ここでは、乱数値計算部14は、i=1,...,nの各整数値iについての値x[i]を結合することにより、疑似乱数を計算する。
乱数値計算部14は、計算した疑似乱数を出力する。

0024

***動作の説明***
図5に基づき、実施の形態1に係る疑似乱数生成装置10の処理を説明する。
実施の形態1に係る疑似乱数生成装置10の処理は、実施の形態1に係る疑似乱数生成方法に相当する。また、実施の形態1に係る疑似乱数生成装置10の処理は、実施の形態1に係る疑似乱数生成プログラムの処理に相当する。

0025

S1の取得処理では、取得部11は、値IV及び秘密鍵Kを取得する。
S2の第1関数F計算処理では、第1関数F計算部121は、S1で取得された値IV及び秘密鍵Kを入力として、関数F[0]により値st[0]を計算する。

0026

i=1,...nの各整数値iについて昇順にS3からS5の処理が実行される。
S3の第2関数F計算処理では、第2関数F計算部122は、値st[i−1]を入力として関数F[i]により値st[i]を計算する。
S4の関数g計算処理では、関数g計算部13は、値st[i−1]のうちの少なくとも一部のビットと、値st[i]のうちの少なくとも一部のビットとを入力として関数g[i]によりr[i]ビットの値x[i]を計算する。
S5の乱数値計算処理では、乱数値計算部14は、値x[i]を結合することにより、疑似乱数を計算する。

0027

S6の乱数値出力処理では、乱数値計算部14は、計算された疑似乱数を出力する。

0028

***効果の説明***
以上のように、実施の形態1に係る疑似乱数生成装置10は、非線形関数F[i]により計算された値st[i]をそのまま利用して疑似乱数を生成せず、非線形関数F[i−1]により計算された値st[i−1]を用いて値st[i]を変換した上で利用して疑似乱数を生成する。つまり、前の非線形関数F[i−1]により計算された値st[i−1]を利用したフィードフォワード演算を行い、疑似乱数を生成する。これにより、非線形関数F[i]により計算された値st[i]を推定することが困難になり、識別不可能性の安全性が値cに依存しないようにすることができる。

0029

また、実施の形態1に係る疑似乱数生成装置10は、非線形関数F[i]により計算された値st[i]を推定することが困難なため、非線形関数F[i]に対して差分攻撃及び線形攻撃が困難になる。そのため、非線形関数F[i]の構造を簡素化しても、差分攻撃及び線形攻撃に対する安全性を担保できるようになる。非線形関数F[i]の構造を簡素化することにより、非線形関数F[i]の計算量を減らすことができ、疑似乱数生成の計算量を減らすことができる。

0030

また、実施の形態1に係る疑似乱数生成装置10が実現する疑似乱数生成関数は、全ての整数値iについての非線形関数F[i]が入出力長がbビットの理想的な非線形関数である場合に、min{b/2,k}ビットの乱数との識別不可能性を持つことを示すことが可能である。また、この場合に、全ての整数値iについての非線形関数F[i]の安全性がb−rの長さに依存しないことを示すことが可能である。

0031

実施の形態2.
実施の形態2では、非線形関数F[i]について説明する。
実施の形態2では、実施の形態1と異なる部分について説明する。

0032

図6に基づき、実施の形態2に係る非線形関数Fの構成について説明する。
非線形関数F[0]は、ブロック暗号を構成する関数である。非線形関数F[0]は、i=1,...,tの各整数値iについてのラウンド関数R[i]と、秘密鍵Kから各ラウンド関数R[i]の入力となる副鍵K[i]を生成する副鍵生成関数とを有する。

0033

非線形関数F[0]では、まず、秘密鍵Kを入力として副鍵生成関数により、i=1,...,tの各整数値iについての副鍵K[i]が生成される。
次に、値IV及び副鍵K[1]を入力としてラウンド関数R[1]により値y[1]が計算される。そして、i=2,...,tの各整数値iについて昇順に、値y[i−1]及び副鍵K[i]を入力としてラウンド関数R[i]により値y[i]が生成される。
非線形関数F[0]では、i=1,...,tの少なくとも一部の整数値iについてのラウンド関数R[i]により計算された値y[i]又はラウンド関数R[i]の内部の値を結合して、値st[0]が計算される。

0034

i=2,...,nの各整数値iについての非線形関数F[i]は、非線形関数F[0]が有するラウンド関数R[i]のうちの少なくとも一部のラウンド関数R[i]と、値st[i−1]から各ラウンド関数R[i]の入力となる副鍵K[i]を生成する関数f[i−1]とを有する関数である。つまり、i=2,...,nの各整数値iについての非線形関数F[i]が有するラウンド関数R[i]は、非線形関数F[0]が有するラウンド関数R[i]から選択された少なくとも一部のラウンド関数R[i]である。ここでは、i=2,...,nの各整数値iについての非線形関数F[i]が有するラウンド関数R[i]を、j=1,...,tiの各整数値jについてのラウンド関数R[i,j]と記載する。

0035

非線形関数F[i]では、まず、値st[i−1]を入力として関数f[i−1]により、値IV[i]と、j=1,...,tiの各整数値jについての副鍵K[i,j]とが生成される。ここでは、関数f[i−1]は、値st[i−1]のビットから選択された一部のビットを初めに計算されるラウンド関数R[i,1]の入力値とし、st[i−1]のビットから選択された一部のビットを各ラウンド関数R[i,j]で使用される副鍵K[i,j]とする。
次に、値IV[i]及び副鍵K[i,1]を入力としてラウンド関数R[i,1]により値y[i,1]が計算される。そして、j=2,...,tiの各整数値jについて昇順に、値y[i,j−1]及び副鍵K[i,j]を入力としてラウンド関数R[i,j]により値y[i,j]が生成される。
非線形関数F[i]では、j=1,...,tiの少なくとも一部の整数値jについてのラウンド関数R[i,j]により計算された値y[i,j]を結合して、値st[j]が計算される。

0036

図7に基づき、実施の形態2に係る非線形関数Fの他の構成について説明する。
図7に示す非線形関数Fについて、図6に示す非線形関数Fと異なる点について説明する。
非線形関数F[0]は、図6に示す非線形関数F[0]と同じブロック暗号を構成する関数を有する。また、非線形関数F[0]は、ブロック暗号が有するラウンド関数R[i]のうちの少なくとも一部のラウンド関数R[i]が順に計算される関数Xを有する。関数Xが有するラウンド関数R[i]は、ブロック暗号が有するラウンド関数R[i]から選択された少なくとも一部のラウンド関数R[i]である。ここでは、関数Xが有するラウンド関数R[i]を、j=1,...,t0の各整数値jについてのラウンド関数[0,j]と記載する。

0037

非線形関数F[0]では、まず、秘密鍵Kを入力として副鍵生成関数により、i=1,...,tの各整数値iについての副鍵K[i]が生成される。
次に、値IV及び副鍵K[1]を入力としてラウンド関数R[1]により値y[1]が計算される。そして、i=2,...,tの各整数値iについて昇順に、値y[i−1]及び副鍵K[i]を入力としてラウンド関数R[i]により値y[i]が生成される。
次に、値y[t]及び副鍵K[0,1]を入力としてラウンド関数R[0,1]により値y[0,1]が計算される。そして、j=2,...,t0の各整数値jについて昇順に、値y[0,j−1]及び副鍵K[0,j]を入力としてラウンド関数R[0,j]により値y[0,j]が計算される。ここで、j=1,...,t0の各整数値jについての副鍵K[0,j]は、ラウンド関数R[0,j]に対応するブロック暗号が有するラウンド関数R[i]に入力された副鍵K[i]である。例えば、ラウンド関数R[0,1]がラウンド関数R[3]であるなら、副鍵K[0,1]は副鍵K[3]である。
非線形関数F[0]では、i=1,...,tの各整数値iについてのラウンド関数R[i]により計算された値y[i]と、j=1,...,t0の各整数値jについてのラウンド関数R[0,j]により計算された値y[0,j]との少なくとも一部を結合して、値st[0]が計算される。

0038

i=2,...,nの各整数値iについての非線形関数F[i]は、図6に示す非線形関数F[i]と同じである。

0039

以上のように、実施の形態2に係る疑似乱数生成装置10では、ブロック暗号を構成する関数、又は、ブロック暗号を構成する関数の部品を、非線形関数Fとしている。特に、実施の形態2に係る疑似乱数生成装置10では、ラウンド関数Rに対する副鍵を固定にせず、非線形関数Fの入力から生成した。また、実施の形態2に係る疑似乱数生成装置10では、ブロック暗号を構成する関数の出力値をそのまま非線形関数Fの出力値とするのではなく、少なくとも一部のラウンド関数Rで計算された値を結合した値を非線形関数Fの出力値とした。
これにより、非線形関数Fの入出力長を長くすることができる。実施の形態1で説明した通り、疑似乱数生成関数は、全ての整数値iについての非線形関数F[i]が入出力長がbビットの理想的な非線形関数である場合に、min{b/2,k}ビットの乱数との識別不可能性を持つことを示すことが可能である。したがって、非線形関数Fの入出力長を長くすることができれば、識別不可能性を持つことを示すことが可能な乱数の長さを長くすることができる。

0040

また、実施の形態2に係る疑似乱数生成装置10では、実施の形態1に係る疑似乱数生成装置10と同様に、フィードフォワード演算を行い、疑似乱数を生成する。そのため、非線形関数Fにより計算された値を推定することが困難である。したがって、非線形関数Fが有するラウンド関数Rの数を減らしても安全性を確保できる。非線形関数Fが有するラウンド関数Rの数を減らすことにより、疑似乱数生成の計算量を減らすことができる。

0041

ここでは、ブロック暗号として、非特許文献3に記載されたAES(Advanced Encryption Standard)を用いることができる。また、ブロック暗号として、非特許文献4に記載されたCamellia(登録商標)を用いることもできる。

0042

ブロック暗号として、AESを用いる場合、全てのラウンド関数はAESのラウンド関数となる。
128bit鍵のAESを用いる場合であって、図6に示す非線形関数Fの構成とする場合、tを10とし、tiを10以下とする。
128bit鍵のAESを用いる場合であって、図7に示す非線形関数Fの構成とする場合、tを10とし、tiを10以下とする。
192bit鍵のAESを用いる場合であって、図6に示す非線形関数Fの構成とする場合、tを12とし、tiを12以下とする。
192bit鍵のAESを用いる場合であって、図7に示す非線形関数Fの構成とする場合、tを12とし、tiを12以下とする。
256bit鍵のAESを用いる場合であって、図6に示す非線形関数Fの構成とする場合、tを14とし、tiを14以下とする。
256bit鍵のAESを用いる場合であって、図7に示す非線形関数Fの構成とする場合、tを14とし、tiを14以下とする。

0043

ブロック暗号として、Camellia(登録商標)を用いる場合、全てのラウンド関数はCamellia(登録商標)のラウンド関数となる。
128bit鍵のCamellia(登録商標)を用いる場合であって、図6に示す非線形関数Fの構成とする場合、tを18とし、tiを18以下とする。また、f[i]は128bit鍵のCamellia(登録商標)の副鍵生成関数を用いてもよい。
128bit鍵のCamellia(登録商標)を用いる場合であって、図7に示す非線形関数Fの構成とする場合、tを18とし、tiを18以下とする。また、f[i]は128bit鍵のCamellia(登録商標)の副鍵生成関数を用いてもよい。
192bit鍵のCamellia(登録商標)を用いる場合であって、図6に示す非線形関数Fの構成とする場合、tを24とし、tiを24以下とする。また、f[i]は192bit鍵のCamellia(登録商標)の副鍵生成関数を用いてもよい。
192bit鍵のCamellia(登録商標)を用いる場合であって、図7に示す非線形関数Fの構成とする場合、tを24とし、tiを24以下とする。また、f[i]は192bit鍵のCamellia(登録商標)の副鍵生成関数を用いてもよい。
256bit鍵のCamellia(登録商標)を用いる場合であって、図6に示す非線形関数Fの構成とする場合、tを24とし、tiを24以下とする。また、f[i]は256bit鍵のCamellia(登録商標)の副鍵生成関数を用いてもよい。
256bit鍵のCamellia(登録商標)を用いる場合であって、図7に示す非線形関数Fの構成とする場合、tを24とし、tiを24以下とする。また、f[i]は256bit鍵のCamellia(登録商標)の副鍵生成関数を用いてもよい。

0044

図8は、実施の形態1,2に係る疑似乱数生成装置10のハードウェア構成例を示す図である。
疑似乱数生成装置10はコンピュータである。
疑似乱数生成装置10は、プロセッサ901、補助記憶装置902、メモリ903、通信装置904、入力インタフェース905、ディスプレイインタフェース906といったハードウェアを備える。
プロセッサ901は、信号線910を介して他のハードウェアと接続され、これら他のハードウェアを制御する。
入力インタフェース905は、ケーブル911により入力装置907に接続されている。
ディスプレイインタフェース906は、ケーブル912によりディスプレイ908に接続されている。

0045

プロセッサ901は、プロセッシングを行うIC(IntegratedCircuit)である。プロセッサ901は、例えば、CPU(Central Processing Unit)、DSP(Digital Signal Processor)、GPU(Graphics Processing Unit)である。
補助記憶装置902は、例えば、ROM(Read Only Memory)、フラッシュメモリ、HDD(Hard Disk Drive)である。
メモリ903は、例えば、RAM(Random Access Memory)である。
通信装置904は、データを受信するレシーバー9041及びデータを送信するトランスミッター9042を含む。通信装置904は、例えば、通信チップ又はNIC(Network Interface Card)である。
入力インタフェース905は、入力装置907のケーブル911が接続されるポートである。入力インタフェース905は、例えば、USB(Universal Serial Bus)端子である。
ディスプレイインタフェース906は、ディスプレイ908のケーブル912が接続されるポートである。ディスプレイインタフェース906は、例えば、USB端子又はHDMI(登録商標)(High Definition Multimedia Interface)端子である。
入力装置907は、例えば、マウスキーボード又はタッチパネルである。
ディスプレイ908は、例えば、LCD(Liquid Crystal Display)である。

0046

補助記憶装置902には、上述した取得部11、関数F計算部12、第1関数F計算部121、第2関数F計算部122、関数g計算部13、乱数値計算部14(以下、取得部11、関数F計算部12、第1関数F計算部121、第2関数F計算部122、関数g計算部13、乱数値計算部14をまとめて「部」と表記する)の機能を実現するプログラムが記憶されている。
このプログラムは、メモリ903にロードされ、プロセッサ901に読み込まれ、プロセッサ901によって実行される。
更に、補助記憶装置902には、OS(Operating System)も記憶されている。
そして、OSの少なくとも一部がメモリ903にロードされ、プロセッサ901はOSを実行しながら、「部」の機能を実現するプログラムを実行する。
図8では、1つのプロセッサ901が図示されているが、疑似乱数生成装置10が複数のプロセッサ901を備えていてもよい。そして、複数のプロセッサ901が「部」の機能を実現するプログラムを連携して実行してもよい。
また、「部」の処理の結果を示す情報やデータや信号値変数値が、メモリ903、補助記憶装置902、又は、プロセッサ901内のレジスタ又はキャッシュメモリファイルとして記憶される。

0047

「部」を「サーキットリー」で提供してもよい。また、「部」を「回路」又は「工程」又は「手順」又は「処理」に読み替えてもよい。「回路」及び「サーキットリー」は、プロセッサ901だけでなく、ロジックIC又はGA(Gate Array)又はASIC(Application Specific IntegratedCircuit)又はFPGA(Field−Programmable Gate Array)といった他の種類の処理回路をも包含する概念である。

0048

10疑似乱数生成装置、11 取得部、12関数F計算部、121 第1関数F計算部、122 第2関数F計算部、13 関数g計算部、14乱数値計算部。

ページトップへ

この技術を出願した法人

この技術を発明した人物

ページトップへ

関連する挑戦したい社会課題

関連する公募課題

ページトップへ

技術視点だけで見ていませんか?

この技術の活用可能性がある分野

分野別動向を把握したい方- 事業化視点で見る -

ページトップへ

おススメ サービス

おススメ astavisionコンテンツ

新着 最近 公開された関連が強い技術

この 技術と関連性が強い技術

関連性が強い 技術一覧

この 技術と関連性が強い人物

関連性が強い人物一覧

この 技術と関連する社会課題

関連する挑戦したい社会課題一覧

この 技術と関連する公募課題

関連する公募課題一覧

astavision 新着記事

サイト情報について

本サービスは、国が公開している情報(公開特許公報、特許整理標準化データ等)を元に構成されています。出典元のデータには一部間違いやノイズがあり、情報の正確さについては保証致しかねます。また一時的に、各データの収録範囲や更新周期によって、一部の情報が正しく表示されないことがございます。当サイトの情報を元にした諸問題、不利益等について当方は何ら責任を負いかねることを予めご承知おきのほど宜しくお願い申し上げます。

主たる情報の出典

特許情報…特許整理標準化データ(XML編)、公開特許公報、特許公報、審決公報、Patent Map Guidance System データ