スライド 1

暗号技術
~公開鍵暗号方式の仕組み~
(3週目)
情報工学科 04A1004
石川 真悟
公開鍵暗号
公開鍵を使って暗号化し、秘密鍵を使って復
号化する。
事前に暗号化する人に公開鍵を渡し、自分が
持っている秘密鍵を使って複合化する。
公開鍵と秘密鍵の2つの鍵を使うことで、対称
暗号方式が持っていた鍵配送問題を解決した。
公開鍵暗号の種類
• RSA(公開鍵暗号で最も普及している)
• ElGamal(離散対数問題を応用した)
• Rabin(RSAを改良して安全性証明をつけ
た)
RSAの暗号化処理
平文の値を「E」回掛け合わせ、この結果の値を「N」で割り、余りの
値を求める。この計算結果が暗号文になる。「E」と「N」は公開鍵
の値になる。
暗号文=平文 Emod N
平文
暗号化処理
暗号文=平文E mod N
暗号文
公開鍵
E
N
例)平文12、E=5、N=221
5
暗号文=12 mod 221
暗号文=207
暗号化処理そのものは、
とてもシンプルだが、
秘密鍵の情報がわからない限り、
現実的な時間で解読するのは困難
RSAの復号化処理
暗号文の値を「D」回掛け合わせ、この結果の値を「N」で割り、余
りの値を求める。この計算結果が暗号文になる。「D」と「N」は秘密
鍵の値になる。
平文=暗号文 Dmod N
暗号文
暗号化処理
平文=暗号文D mod N
平文
秘密鍵
D
N
例)暗号文207、D=29、N=221
29
平文=207 mod 221
平文=12
暗号化処理同様、
復号化処理もとてもシンプルなため、
秘密鍵が他の人の手に渡ると
解読は簡単にできてしまうため、
秘密鍵は厳重に管理する必要がある。
キーペアの生成手順
公開鍵と秘密鍵は対(ペア)になっている必要が
あり、この2つのキーのことをキーペアと呼ぶ。
PとQを使ってNを計算する
N=PxQ
PとQを使ってLを計算する
L=1cm(P-1,Q-1)
P-1とQ-1の最小公倍数
Lを使ってEを計算する
EとLを使ってDを計算する
1<E<L god(E,L)=1
EとLの最大公約数が1になるEを求める
E x D mod L =1
EとDを掛けmodLを計算した値が
1になるようにDを求める
キーペアの生成の具体例
まずPとQの2つの素数を用意(説明を簡単にするため小さい数字で行なう)
P=13、Q=17
N=PxQ=13x17=221
L=1cm(P-1,Q-1)=1cm(13-1,17-1)=1cm(12,16)
12と16の最小公倍数は48なのでL=48
1<E<L god(E,L)=1
God(E,48)=1
Eと48の最大公約数が1になるようなEを求める。
E=5,7,11,13,17,19,23,25,29,31,35,37,41,43,47
この中から素数を1つを選ぶ。ただし、25、35は素数ではないので外す。
仮に5を選ぶ。
ExD mod L=1
5xD mod 48=1
D=29
ElGamalの暗号化処理
K=P-1と互いに素な乱数
暗号文a=G Kmod P
暗号文b=Y K平文mod P
この暗号文aと暗号文bがペアになって1つの暗号文になる。
例)平文12、G=13、Y=4、P=17
G,Y,Pが公開鍵の値になる。
平文
暗号化処理
K=P-1と互いに素な乱数
暗号文a=G k mod P
k
暗号文b=Y 平文mod P
暗号文
公開鍵
G
Y
P
K=(17-1)と互いに素な乱数
K=3,5,7,11,13
この中から1つ選択
暗号文a=133 mod 17=4
暗号文b=43 x12 mod 17=3
ElGamalの復号化処理
平文x暗号文a x mod P=暗号文b
XとPが秘密鍵の値になる。
暗号文
秘密鍵
暗号化処理
X
P
x
平文x暗号文a mod P=暗号文b
平文
例)暗号文a=4、暗号文b=3、
X=11、P=17
平文x411mod 17=3
平文=12
キーペアの生成手順
まず1つの大きな素数を準備。
この1つの素数をPとしてG、Y、Xを計算で生成。
G、Y、Pが公開鍵、X、Pが秘密鍵
Pを使ってGを計算する
Pを使ってXを計算する
PとGとXを使ってYを計算する
G<P
X<P
Y=Gx mod P
キーペアの生成の具体例
まず素数Pを用意(説明を簡単にするため小さい数字で行なう)
P=17
G<P
G<17
仮にG=13とする。
X<P
X<17
仮にX=11とする。
11
Y=G mod P
11
=13 mod 17
=4
Rabinの暗号化処理
暗号文=平文x(平文+B) mod N
BとNが公開鍵になる。
平文
暗号化処理
公開鍵
B
N
暗号文=平文x(平文+B) mod N
暗号文
例)平文135、B=201、N=209
暗号文=135x(135+201)mod 209
暗号文=7
Rabinの復号化処理
2
(平文 +平文xB-暗号文) mod P=0
2
(平文 +平文xB-暗号文) mod Q=0
この連立方程式を満たす平文の値を求める。
BとPとQが秘密鍵になる。
秘密鍵
暗号文
2
B
暗号化処理
P
Q
(平文 +平文xB-暗号文) mod P=0
2
(平文 +平文xB-暗号文) mod Q=0
平文
例)暗号文7、B=201、P=11、Q=19
(平文2 +平文x201-7) mod 11=0
2
(平文 +平文x201-7) mod 19=0
平文=135
キーペアの生成手順
まず2つの大きな素数を準備。
この2つの素数をP、QとしてNとBを計算で生成。
B,Nが公開鍵、B,P,Qが秘密鍵
PとQを使ってNを計算する
Nを使ってBを計算する
N=PxQ
B<N
キーペアの生成の具体例
まず素数PとQを用意(説明を簡単にするため小さい数字で行なう)
P=11、Q=19
N=PxQ
=11x19
=209
B<N
B<209
仮に値を決める。