Nを共有しないRSA Key Generationの紹介

Nを共有しないRSA Key Generationの紹介 お知らせ
Table of Content

本稿では、この論文を扱います。
https://link.springer.com/content/pdf/10.1007%2F3-540-48405-1_8.pdf

この記事で紹介する内容

公開鍵暗号アルゴリズムであるRSAのプロトコルの一つであるBoneh-Franckrinプロトコルの改良として二つの素数の積Nを共有することなく送信者、受信者の2人が共同で公開鍵と秘密鍵を生成するプロトコルを示す

Boneh-Franckrinプロトコルの流れ

1.候補の選択

 AliceがP_a, Q_a 、BobがP_b,Q_bを独立して選びP=P_a+P_b ,Q=Q_a+Q_bを候補とする

2.Nを計算
 AliceとBobの両者がN=PQを計算する

3.初期の素数判定
 k個(k番目の素数までをかけると2^σを初めて超える)の小さな素数のそれぞれについてNがそれらで割り切れるかを調べる。

4.全ての素数判定

5.dの計算と共有
 両当事者間で既知であるeを用いて解読指数dを計算する

Nを共有することのないプログラムへの改良

ここでは

・Nの計算
・初期の素数判定 
の部分を改良する

Nの計算

AliceはP_a,Q_bをBobはP_b,Q_bを持っている。このときAliceのみが秘密裏にN=(P_a+P_b)(Q_a+Q_b) = P_aQ_a + P_aQ_b + P_bQ_a + P_bQ_bを計算する

一つ目の方法
$a,b∈R$である公に知られている環Rを導入し、Aliceが$a$をBobがbを持っているとする。このときx+y=abとなるxをAliceが、yをBobがoblivious transferによって得ることでNを求めることができる

二つ目の方法
素数p>2^σとしGF(p)を設定することでNを求める

三つ目の方法
Homomorphic encryptionを用いてNを求める

初期の素数判定

候補Nが最初のk個の素数p_1,p_2,…,p_kのうちの一つで割り切れるかどうかを判定し、P,Qが素数であるかを判定する
ここではある候補が初期の素数判定に失敗した場合に、新たな候補を見つけだす際のより効率的な方法が2つ示されている

一つ目の方法
ある候補Nが捨てられた後、Aliceは前のP_a,Q_aを持ったままBobが新たなP_b,Q_bを選択することで新たな候補Nを見つけ出す。

二つ目の方法
homomorphic encryption protocolを用いてP_a,P_b,Q_a,Q_b mod p_iを選びN mod p_iを再計算する
この確率はP_a,P_b,Q_a,Q_bを選ぶ時よりも少なくなる

このプロトコルの性能

このNを共有することのないプロトコルの性能はσ=1024の時 実行時間はBoneh-Franklinプロトコルの約10倍以下、通信の複雑さは約42MB(改良した場合29MB)

タイトルとURLをコピーしました