100倍高速に安全な暗号・認証鍵を生成

[ PRESS RELEASE ]

2002-0214
平成14年9月12日
株式会社富士通研究所

No.165

100倍高速に安全な暗号・認証鍵を生成

～疑似乱数生成アルゴリズム"SR2002"を開発～

株式会社富士通研究所(社長：藤崎道雄、本社：川崎市)は、暗号技術や認証技術で必須となる、安全性と高速性とを兼ね備えた新しい疑似乱数(*1)の生成方法 "SR2002"を開発いたしました。

"SR2002"は、新しく生成される疑似乱数の予測が理論的に不可能なため、e-Japan重点計画等で用いられるPKI(Public Key Infrastructure)による個人認証等を、さらに安全にできるものと期待されます。なお、本技術の詳細は、電子情報通信学会情報セキュリティ研究会(9月20日、機械振興会館(東京都港区芝公園3-5-8))にて発表する予定です。

【開発の背景】

ブロードバンド・インターネットが普及しはじめ、インターネット上を商取引情報や個人のプライバシー情報などの重要な情報が流れるようになっています。しかし、インターネットを流れる情報は、理論上は第三者でも見ることができるため、重要な情報を守るための暗号化や個人認証などの技術が必要になっています。

暗号や認証技術で使用される暗号鍵は、一般的に計算機で生成した疑似乱数を用いて作られますが、疑似乱数に偏りが存在したり、一度使われた疑似乱数から次に生成される疑似乱数が予想できたりする場合があります。こういった疑似乱数を用いると、暗号鍵が予想されてしまい、安全性を根幹から揺るがすことになります。

しかし、安全性を重視するあまり実用的な時間で疑似乱数を生成できないと実用には適しません。そこで、安全かつ高速に疑似乱数を生成可能な技術が望まれていました。

【開発した技術】

今回開発した擬似乱数生成アルゴリズム"SR2002"は、ある乱数の次に生成される乱数が理論的に予測不可能であることが証明できるアルゴリズムを使っています。さらに、乱数を生成する際に用いる非線形変換を高速に実行できる技術の開発に成功し、従来法では難しかった安全かつ高速な擬似乱数生成を実現しました。

開発した技術の特長は次の通りです。

高い安全性

SR2002では、擬似乱数を安全に生成するための核となる非線形変換に、「離散対数問題(*2)」と呼ばれる数学的問題に基づく方法を利用しており、本方式で生成した擬似乱数が予測不可能であることを数学的に証明可能です。
高速性

SR2002では、通常は長い時間がかかる非線形変換の計算に、特殊な線形変換を利用することで高速な疑似乱数生成を実現しています。
SR2002は、予測不可能であることの証明ができていない米国標準の擬似乱数生成方式(FIPS186-2 (*3))と同等以上の速度性能を実現しました(当社比)。
さらに、予測不可能であることが証明可能な従来の高速擬似乱数生成法 Blum-Blum-Shub 法(*4)と比較すると100倍以上の速度性能(当社比)を達成しました。
今後は、暗号化によるセキュア通信やPKIによる認証システムなどへの適用を図っていく予定です。

【用語解説または注釈】

*1 疑似乱数: 真性乱数と区別が付きにくい乱数のことで、ソフトウェアで実現可能なため、真性乱数に替わるものとしてしばしば利用されます。
*2 離散対数問題: 数学的な群構造の要素yと生成元と呼ばれる特殊な要素gからy=g^xを満たす整数xを求める問題のことで、多くの研究者はこの問題を効率的に計算することは困難と予想しています。実際に、幾つかの暗号の安全性はこの問題の計算の困難性に基づいています。
*3 FIPS: Federal Information Processing Standard の略称で、米国標準を定めています。
*4 Blum-Blum-Shub法: 予測不可能性が証明できる擬似乱数生成方式の一つで、発案者の名前をとって呼ばれています。また、頭文字をとってBBS法とも呼ばれています。安全性の根拠は素因数分解問題の困難性に基づいています。予測困難性が証明できる手法の中では高速な手法として有名です。今回の速度比較では、1024ビットの素因数分解問題相当の安全性を計算した場合の比較を行っています。

以上

プレスリリースに記載された製品の価格、仕様、サービス内容、お問い合わせ先などは、発表日現在のものです。その後予告なしに変更されることがあります。あらかじめご了承ください。ご不明な場合は、富士通お客様総合センターにお問い合わせください。