RSA-lecture-2015.pptx

全文

(1)公開鍵暗号�RSAについて 3年授業「情報ネットワーク」授業スライドより抜粋� 豊橋技術科学大学. 情報・知能工学系. 梅村恭司. 2015-06-24 . �. Copyright 2014 Kyoji Umemura (http://www.ss.cs.tut.ac.jp/). 出典を明らかにしていただければ、自由に授業／セミナー等で. 使っていただいて結構です。�.

(2) これからのスライドは下記を参考に，Javaでプログラミングしながら，作成しました。 � 岡本栄司著，� 暗号理論入門[第2版] 共立出版株式会社�.

(3) RSA暗号とネットワーク� • 暗号化と復号の鍵を別にして，かつ，暗号化の鍵を公開できると便利. • 計算量という壁を使って，上記を実現したものの代表がRSA暗号. • これを理解するには，整数論の知識が必要：「ある整数で割った余りで等しい整数の体系」を扱う�.

(4) JavaのBigIntegerクラス� • import java.math.BigInteger;. • x = new BigInteger("1234567");. • System.out.println(x.toString());.

(5) 剰余系� • 17 = 22 (mod 5). • 数を5で割ったあまりで比較すれば，17と22 は同じ. • (mod 5)は比較の方法を記述. – あまりをとる演算子ではない。.

(6) BigPowerのデモ� • （mod n) で， aのx乗を計算するプログラム. ％ java BigPower. 1000�2�9. 1000�2�9�512. 1000�2�10. 1000�2�10�24.

(7) RSA暗号の例� • 大きな素数2つ(秘密）からnと鍵を二つ生成する。�e: encode_key, d: decode_key. n=10002200057(公開）, e=20003（公開）,. d=2564628215（秘密）. ベキ乗演算で暗号化�c=me(mod n). ベキ乗演算で復号�m'=cd(mod n). ��つまりm'=cd=med (mod n)��. このとき，�m'=m (mod n)�が成立する：デモ�.

(8) RSA:n = 10, e = 3, d = 3 暗号化(板書)� 13 = 1 (mod 10). 23 = 8 (mod 10). 33 = 7 (mod 10). 43 = 4 (mod 10). 53 = 5 (mod 10). 63 = 6 (mod 10). 73 = 3 (mod 10). 83 = 2 (mod 10). 93 = 9 (mod 10).

(9) RSA:n = 10, e = 3, d = 3 復号(板書)� 13 = 1 (mod 10). 23 = 8 (mod 10). 33 = 7 (mod 10). 43 = 4 (mod 10). 53 = 5 (mod 10). 63 = 6 (mod 10). 73 = 3 (mod 10). 83 = 2 (mod 10). 93 = 9 (mod 10). 13 = 1 (mod 10). 83 = 2 (mod 10). 73 = 3 (mod 10). 43 = 4 (mod 10). 53 = 5 (mod 10). 63 = 6 (mod 10). 33 = 7 (mod 10). 23 = 8 (mod 10) . 93 = 9 (mod 10).

(10) 素朴な疑問� – 10002200057(公開）, 20003（公開）, 2564628215（秘密）. • ベキ乗演算で暗号化. • ベキ乗演算で復号�. どうして、通信できるのか。。。。. �説明には有限体の知識が必要�.

(11) 剰余系� • 12 = 22 (mod 10). • 数を10で割ったあまりで比較すれば，12と 22は同じ. • (mod 10)は比較の方法を記述したもの. – 「等しい」という関係を修飾している。. 11.

(12) a = b (mod n)� • nで割った余りを問題にするならば，aとbは等しい. 直感的にわからなかったら，n=10とする。これは，整数の一番下の桁で整数を比較することになる。.

(13) a = b (mod n)� • nで割った余りを問題にするならば，aとbは等しい. ∀a; a = a(mod n) 反射律. ∀a; ∀b; a = b(mod n) →�b = a (mod n) 対称律. ∀a; ∀b； ∀c；. �a=b(mod n)かつb=c(mod n). �→�a=c (mod n) 推移律.

(14) a = b (mod n)� • nで割った余りを問題にするならば，aとbは等しい. 整数は，n個のグループに分類されるが，そのグループのなまえに，0からn-1までの整数を使う。これは，グループの名前であることに注意する必要がある。.

(15) 加算� • a=b (mod n) ならば，. ��∀z�整数，�a+z = b+z (mod n). 直感的にわからなかったら，n=10とする。これは，整数の一番下の桁で整数を比較することになる。. グループの名前を求めるには，通常の加算をして，下の桁だけを使うことでよい。.

(16) 減算� • a=b (mod n) ならば，. ��∀z�整数，�a-z = b-z (mod n). 直感的にわからなかったら，n=10とする。これは，整数の一番下の桁で整数を比較することになる。. グループの名前を求めるには，負にならないように10を加算することをして，一番したの桁を使うことでよい。.

(17) 乗算� • a=b (mod n) ならば，. ��∀z�整数，�z×a = z×b (mod n). 直感的にわからなかったら，n=10とする。これは，整数の一番下の桁で整数を比較することになる。. グループの名前を求めるには，通常の乗算をして，一番下の桁だけを使うことでよい。.

(18) 逆数�(mod 10)� 3×7�= 1 (mod 10). よって，3-1 ＝7 (mod 10). �注意�逆数は通常の意味と大きく異なる。. 演習，下記のxをもとめてみよう。. x = 1-1 (mod 10) . x = 7-1 (mod 10) . x = 9-1 (mod 10) �.

(19) 逆数 (mod 10)� 1 = 1-1 (mod 10) . 3 = 7-1 (mod 10) . 9 = 9-1 (mod 10) . 注意， 0, 及び，10と互いに素でない数，. x = 0-1 �(mod 10) . x = 2-1 (mod 10) . x = 5-1 (mod 10) . を満たすxは存在しない。�.

(20) 逆数：�(mod 5)� 3×2�= 1 (mod 5). よって，3-1 ＝2 (mod 5). �注意�逆数は通常の意味と大きく異なる。. 演習，下記のxをもとめてみよう。. x = 1-1 (mod 5) . x = 2-1 (mod 5) . x = 4-1 (mod 5) �.

(21) 逆数 (mod 5)� 1 = 1-1 (mod 5) . 3 = 2-1 (mod 5) . 2 = 3-1 (mod 5) . 4 = 4-1 (mod�5) . どのように求めた？�（順番に条件を満たすか検査したと思う。。。）. 注意，x = 0-1 �(mod 5) . を満たすxは存在しない。.

(22) 逆数 (mod 素数p)� n=1, 2, .... , p-1について，. x = n-1 �(mod p) となる，xがある。. 注意，n≠0である。. x = 0-1 �(mod p) . を満たすxは存在しない。.

(23) 割り算 (mod 素数p)� n=1, 2, .... , p-1について，. x = n-1 �(mod p) となる，xがある。. y/n は，y×n-1と考える。�（掛け算の逆演算）. すると，0以外の数で割り算した結果が存在する。�（整数はみたさないが，有理数や実数が満たす性質：�集合と加算と乗算が「体」である）.

(24) 整数をあまりでグループ分けする。グループに名前をつける。 � �「5で割ったあまりが0の整数」を"0"と書くことにする。. "1", "2", "3", "4" も同様， � つまり， "1"は，{ 1, 6, 11, 16, .... }のグループのこと，. グループは5つある。�演算は表にできる。. +�. 0�. 1�. 2�. 3�. 4�. ×�. 0�. 1�. 2�. 3�. 4�. 0�. 0�. 1�. 2�. 3�. 4�. 0�. 0�. 0�. 0�. 0�. 0�. 1�. 1�. 2�. 3�. 4�. 0�. 1�. 0�. 1�. 2�. 3�. 4�. 2�. 2�. 3�. 4�. 0�. 1�. 2�. 0�. 2�. 4�. 1�. 3�. 3�. 3�. 4�. 0�. 1�. 2�. 3�. 0�. 3�. 1�. 4�. 2�. 4�. 4�. 0�. 1�. 2�. 3�. 4�. 0�. 4�. 3�. 2�. 1�. 24.

(25) グループでの足し算と掛け算表�. +�. 0�. 1�. 2�. 3�. 4�. ×�. 0�. 1�. 2�. 3�. 4�. 0�. 0�. 1�. 2�. 3�. 4�. 0�. 0�. 0�. 0�. 0�. 0�. 1�. 1�. 2�. 3�. 4�. 0�. 1�. 0�. 1�. 2�. 3�. 4�. 2�. 2�. 3�. 4�. 0�. 1�. 2�. 0�. 2�. 4�. 1�. 3�. 3�. 3�. 4�. 0�. 1�. 2�. 3�. 0�. 3�. 1�. 4�. 2�. 4�. 4�. 0�. 1�. 2�. 3�. 4�. 0�. 4�. 3�. 2�. 1�. 25.

(26) 「負の数」と「逆数」� この演算表では，. �−2は3と考えると考えることができる。. ��2−1は，�3と考えることができる。��. +�. 0�. 1�. 2�. 3�. 4�. ×�. 0�. 1�. 2�. 3�. 4�. 0�. 0�. 1�. 2�. 3�. 4�. 0�. 0�. 0�. 0�. 0�. 0�. 1�. 1�. 2�. 3�. 4�. 0�. 1�. 0�. 1�. 2�. 3�. 4�. 2�. 2�. 3�. 4�. 0�. 1�. 2�. 0�. 2�. 4�. 1�. 3�. 3�. 3�. 4�. 0�. 1�. 2�. 3�. 0�. 3�. 1�. 4�. 2�. 4�. 4�. 0�. 1�. 2�. 3�. 4�. 0�. 4�. 3�. 2�. 1�. 26.

(27) 有限体� 「体」とは、数の集合と演算の組合わさったもののである，ある性質をもつものの名前である。「体」の重要な性質の一つは，ある数の乗算に逆演算となる数が存在する数が、0以外には存在することである。逆演算となる数があることが復号で役立つ。. 有限の集合での「乗算」の体系に「逆数」が存在するのは，面白い性質。. 27.

(28) RSA暗号の例（再度）� • 大きな素数2つ(秘密）からnと鍵を二つ生成する。e: encode_key, d: decode_key. n=10002200057(公開）, e=20003（公開）,. d=2564628215（秘密）. ベキ乗演算で暗号化�c=me(mod n). ベキ乗演算で復号�m'=cd(mod n). ��つまりm'=cd=med (mod n)��. このとき，�m'=m (mod n)�が成立する。� 28.

(29) フェルマーの小定理 . • pが素数のとき，ap-1=1 (mod p). ��ただし，�a=1, 2, ... p-1. • どのような定理か. aがどれであっても，aをp−1回掛ける（ベキ乗する）と1になることが運命付けられている。. p=5のときを計算してみよう。. 29.

(30) p(=5)のときのフェルマーの小定理の確認� • p(=5)が素数のとき，ap-1=1 (mod p). ��ただし，�a=1, 2, ... p-1. 確認してみる。. 1×1×1×1＝1→�1. 2×2×2×2＝4×4＝16�→�1. 3×3×3×3＝9×9＝81�→1�. 4×4×4×4=16×16＝256�→�1. 注意：0のときは成立しない。. ��0×0×0×0＝0なので、0p-1≠1 (mod p). 30.

(31) 観測：p=5では naの集合とaの集合に 1対1対応が存在する. p(=5)は素数. aとnは，1からp-1まで整数とする。. Sは1からp-1までの整数の集合とする。. 任意のaに対し、. ×� 0� 1� 2� 0� 0� 0� 0� ��nとan に(mod p)での. 1� 0� 1� 2� ��1対1対応が存在する 2� 0� 2� 4� 3� 0� 3� 1�. 4�. 0�. 4�. 3�. 3�. 4�. 0�. 0�. 3�. 4�. 1�. 3�. 4�. 2�. 2�. 1�.

(32) 観測：p=5では，�0でないaには，逆数が存在存在する。. p(=5)は素数. aは，1からp-1まで整数とする。. Sは1からp-1までの整数の集合とする。. 任意のaに対して，�. ×� 0� 1� 2� 3�. ��an=1 (mod p)となる 0� 0� 0� 0� 0� 1� 0� 1� 2� 3� ��nが存在する。. 2� 0� 2� 4� 1�. 4� 0� 4� 3�. 3�. 0�. 3�. 1�. 4�. 2�. 4�. 0�. 4�. 3�. 2�. 1�.

(33) フェルマーの小定理の証明の準備（1） . pは素数とする。. a�≠�0 (mod p), x�≠�0 (mod p)である整数a, xについて、ax�≠�0 (mod p). 「つまり、aとxがpの倍数でないとき、axもpの倍数でない。」. ◯ax = 0 (mod p)とすると、. ��1以下p−1以下の整数�nがあって、�ax = np. 素因数分解するととaかxがpの倍数であることになり、仮定と矛盾する。.

(34) フェルマーの小定理の証明の準備（2） . pは素数とする。. aは，1以上p-1以下の整数とする。. x、yは1以上p-1以下の異なる整数とする。. ×� 0� 1� 2� 3� すると、ax�≠�ay (mod p). 0� 0� 0� 0� 0�. 1� 0� 1� 2� 3� つまり、0でないx,yで異なるx, y 2� 0� 2� 4� 1� 3� 0� 3� 1� 4� をa倍した結果をpで割った余ま 4� 0� 4� 3� 2� りは異なるということを意味している。. 4� 0� 4� 3� 2� 1�.

(35) フェルマーの小定理の証明の準備（2） . pは素数とする。. aは，1以上p-1以下の整数とする。. x、yは1以上p-1以下の異なる整数とする。. すると、ax�≠�ay (mod p). 証明 1. �仮定より(x-y) ≠ 0 (mod p), . 2. 仮定より、a ≠ 0 (mod p). 3. よって、a(x-y) ≠ 0 (mod p)であり、. ��ax�≠�ay (mod p)となる。.

(36) フェルマーの小定理の証明の準備(3) . pは素数とする。. aは，1からp-1まで整数とする。. Sは1からp-1までの整数の集合とする。. T(a)={m | n∈S, m∈S, m=na (mod p)}なる集合T(a)を考える。すると、|T(a) |= |S| = p-1. 証明：. nごとに対応するmは異なるので，T(a)の要素の個数はSと同じp-1になる。.

(37) フェルマーの小定理の証明の準備(4) ×�0� 0�0� 1�0� 2�0� 1� 0� 1� 2� pは素数とする。. 2� 0� 2� 4� 3� 0� 3� 1� aは，1からp-1まで整数とする。. 4� 0� 4� 3� Sは1からp-1までの整数の集合とする。. T(a)={m | n∈S, m∈S, m=na (mod p) }とする。. 任意のaについて，T(a)=S. 証明：明らかにT(a) ⊂Sであり，一方|T(a) |= |S| . 3�. 4�. 0�. 0�. 3�. 4�. 1�. 3�. 4�. 2�. 2�. 1�.

(38) フェルマーの小定理の証明の準備(5) ×�0� 0�0� 1�0� 2�0�. 3�. 4�. 0�. 0�. 1� 0� 1� 2� 3� pを素数とする。. 2� 0� 2� 4� 1� 3� 0� 3� 1� 4� a, nは，1からp-1まで整数とする。. 4� 0� 4� 3� 2� Sは1からp-1までの整数の集合とする。. 任意のaに対しあるnが存在して1 = na (mod p). 証明. ��T(a)={m | n∈S, m∈S, m=na (mod p) }とする。. � 1∈S，より1∈T(a), よって，∃n, 1=na (mod p). 4� 3� 2� 1�.

(39) フェルマーの定理（実演） . • pが素数のとき ap-1=1 (mod p). aは�1からp-1まで，�どれでも成立する。�. （p=100003�で実験）. �. 39.

(40) a の集合と �anの集合が等しい。 0を除いて全部掛け合わせてみる。� • 掛け合わせる対象の集合をSとする。. ��S＝{1,2,...., p-1}� ×�. 0�. 1�. 2�. 3�. 4�. 0�. 0�. 0�. 0�. 0�. 1�. 0�. 1�. 2�. 3�. 4�. 2�. 0�. 2�. 4�. 1�. 3�. 3�. 0�. 3�. 1�. 4�. 2�. 4�. 0�. 4�. 3�. 2�. 1�. 0�. 。�.

(41) nと a×nがS上で1対1に対応している。全部掛け合わせる。� ∏ n∈T (a). ∏ n∈T (a). n = ∏ an(mod p) n∈S. n = a p−1 ∏ n(mod p) n∈S. p−1 n = a ∏ ∏ n(mod p) n∈S. n∈S. T(a)=S={1,2,...., p-1}. pが素数なので、b�� ∏ n =1�(mod p)となるbが存在するので，. n∈S. p −1 それを右から掛けると，� 1 = a (mod p).

(42) フェルマーの小定理の系（☆）. • pが素数、λがp-1の倍数のとき，aλ＋1=a (mod p). ��注意：aが任意の整数で成立. ��aの制限がないので，使いやすい。. また，記憶しやすい。. �. 42.

(43) ベキ乗の計算�pの5乗�(mod 5)� • p(=5)が素数のとき，ap=a (mod p). 0×0×0×0×0=0 →�0. 1×1×1×1×1=1 →�1. 2×2×2×2×2＝4×4×2＝32�→2. 3×3×3×3×3＝9×9×3＝81×3＝283�→3. 4×4×4×4×4=16×16×4＝256×4＝1024�→�4. aが0のときも成立する。. 9乗，13乗もおなじようにもとにもどる。. 43.

(44) フェルマーの小定理の系（☆）の証明. pが素数、λがp-1の倍数のとき，aλ＋1=a (mod p). 証明：ある整数kをaをpで割ったときの商とする。. （1）a=kp のとき，明らかに aλ＋1=kλ＋1pλ＋1=0 (mod p). またa=0 (mod p) よって，aλ＋1=a (mod p). （2）a=kp+b�ただし，�b∈{1,2, ..., p-1}のとき. �フェルマの小定理より，�b（p-1)=1(mod p)なので，. ��aλ＋1=bλ＋1=bK（p−1）＋1=(b（p−1） )Kb=1Kb (mod p). 一方，a=b (mod p)�よって， aλ＋1=a (mod p). 44. �.

(45) 中国人の剰余定理 �. pとqが互いに素（最大公約数が1)とする。. またn=pqとする。. �ある数x, yが x=y (mod p)かつ，x=y (mod q)であれば，x=y (mod n). �. q(=5)�. p(=2)�. 0�. 1�. 2�. 3�. 4�. 0�. 0�. 6�. 2�. 8�. 4�. 1�. 5�. 1�. 7�. 3�. 9�. n(=10)�. ある数の5で割ったあまりと，奇数／偶数がわかれば，1桁目がわかる。�.

(46) 中国人の剰余定理 �. pとqが互いに素でないときは. n=pqとして，. �ある数x, yが x=y (mod p)かつ，x=y (mod q)であってもx=y (mod n)とはいえない。. �. q(=4)�. p(=2)�. 0�. 1�. 2�. 3�. 0�. 0, 4�. -�. 2, 6�. -�. 1�. -�. 1, 5�. -�. 3, 7�. n(=8)�.

(47) 中国人の剰余定理（証明の準備）� pとqが互いに素（最大公倍数が1)とする。. またn=pqとする。. �ある数zが z=0 (mod p)かつ z=0 (mod q)であれば，z=0 (mod n)である。. 証明、. zはpとqの公倍数である。pとqは互いに素なので，pとqの最小公倍数はpqつまりnである。. ��よって，ある整数kに対しz=knと表現できるので，. z=0(mod n) となる。�.

(48) 中国人の剰余定理／証明 �. �. pとqが互いに素とする。またn=pqとする。. ある数x, yが x=y (mod p)かつ，x=y (mod q)とする。. (x-y) =0 (mod p), かつ�(x-y) = 0 (mod q)である。. よって， (x-y) = 0 (mod n)となる。. したがって， x = y (mod n).

(49) 二つの素数に関わる性質（☆☆） . • pとqが素数のとき λをp-1とq-1の最小公倍数とすると，�. 任意の整数K、aについてaKλ+1=a (mod pq). . 49.

(50) p(=2)とq(=5)が素数のとき λをp-1と λ+1 q-1の倍数とすると，�a =a (mod pq). 03 = 0 (mod 10). 13 = 1 (mod 10). 23 = 8 (mod 10). 33 = 7 (mod 10). 43 = 4 (mod 10). 53 = 5 (mod 10). 63 = 6 (mod 10). 73 = 3 (mod 10). 83 = 2 (mod 10). 93 = 9 (mod 10). 04 = 0 (mod 10). 14 = 1 (mod 10). 24 = 6 (mod 10). 34 = 1 (mod 10). 44 = 6 (mod 10). 54 = 5 (mod 10). 64 = 6 (mod 10). 74 = 1 (mod 10). 84 = 6 (mod 10). 94 = 1 (mod 10). 05 = 0 (mod 10). 15 = 1 (mod 10). 25 = 2 (mod 10). 35 = 3 (mod 10). 45 = 4(mod 10). 55 = 5 (mod 10). 65 = 6 (mod 10). 75 = 7 (mod 10). 85 = 8 (mod 10). 95 = 9 (mod 10).

(51) 二つの素数に関わる性質の証明. • pとqが素数のとき λをp-1とq-1の最小公倍数とすると，任意の整数Kについて. ��aKλ+1=a (mod pq). 証明：b=aKλ+1とする。�. �Kλはp-1の倍数であるので（☆）より. ��b=aKλ+1=a (mod p）. Kλはq-1の倍数でもあるので，�b=aKλ+1=a (mod q）. pとqは互いに素であるので，中国人の剰余定理に 51. より，�b=aKλ+1=a (mod pq）. �.

(52) RSA暗号� • フェルマーの定理. • ユークリッドの互除法と拡張. これらをつかって，�2つの大きな素数から. �上手にn , e, dを生成する. �. n=10002200057(公開）, e=20003（公開）,. d=2564628215（秘密）. e: encode, d:decode. 52.

(53) RSA:鍵の生成�� • 大きな素数p, qを決める. • λをp-1とq-1の最小公倍数とする。. • eをλと互いに素な数として決める。. • ed = 1(mod λ)となる dを求める。. n(= pq)とeを公開する。(他は秘密とする）. これから，�具体的に計算してみる．�.

(54) RSA:鍵の生成� • 素数p, qを決める：�p=2, q=5�.

(55) RSA:鍵の生成� • 素数p, qを決める：�p=2, q=5. • λをp-1とq-1の最小公倍数(= 4 )とする．.

(56) RSA:鍵の生成� • 素数p, qを決める：�p=2, q=5. • λをp-1とq-1の最小公倍数 (=4)とする．. • eをλと互いに素な数: たとえば3とする．. （互いに素：最大公約数が1であること）.

(57) RSA:鍵の生成� • 素数p, qを決める：�p=2, q=5. • λをp-1とq-1の最小公倍数 (=4)とする．. • eをλ（=4)と互いに素な数: たとえば�3とする．. （互いに素：最大公約数が1であること）. • ed(mod λ)=1となるdをもとめ，d:3とする．. 3×3 =1 (mod 4). 注：ここでは順番にテストしてもとめるが，. ��効率のよい方法がある。.

(58) RSA:鍵の生成� • • • • . 素数p, qを決める：�p=2, q=5. λをp-1とq-1の最小公倍数 (4)とする．. eをλと互いに素な数: 3とする．. ed(mod λ)=1となるdをもとめ，d:3とする．. 1= 3×3 (mod 4) . n = 10, e = 3, d = 3. (注：�e: encode, d: decode）.

(59) RSA:n = 10, e = 3, d = 3 暗号化� 13 = 1 (mod 10). 23 = 8 (mod 10). 33 = 7 (mod 10). 43 = 4 (mod 10). 53 = 5 (mod 10). 63 = 6 (mod 10). 73 = 3 (mod 10). 83 = 2 (mod 10). 93 = 9 (mod 10).

(60) RSA:n = 10, e = 3, d = 3 復号� 13 = 1 (mod 10). 23 = 8 (mod 10). 33 = 7 (mod 10). 43 = 4 (mod 10). 53 = 5 (mod 10). 63 = 6 (mod 10). 73 = 3 (mod 10). 83 = 2 (mod 10). 93 = 9 (mod 10). 13 = 1 (mod 10). 83 = 2 (mod 10). 73 = 3 (mod 10). 43 = 4 (mod 10). 53 = 5 (mod 10). 63 = 6 (mod 10). 33 = 7 (mod 10). 23 = 8 (mod 10) . 93 = 9 (mod 10).

(61) RSA:鍵の生成� • 大きな素数p, qを決める：�p=100003, q=100019�.

(62) RSA:鍵の生成� • 大きな素数p, qを決める：�p=100003, q=100019. • λをp-1とq-1の公倍数 (10002000036)とする．.

(63) RSA:鍵の生成� • 大きな素数p, qを決める：�p=100003, q=100019. • λをp-1とq-1の公倍数 (10002000036)とする．. • eをλと互いに素な数: 20003とする．. （互いに素：最大公約数が1であること）.

(64) RSA:鍵の生成� • • • • . 大きな素数p, qを決める：�p=100003, q=100019. λをp-1とq-1の公倍数 (10002000036)とする．. eをλと互いに素な数: 20003とする．. ed=1(mod λ)となるdをもとめ，d:2564628215とする．. 1= 20003×2564628215 (mod 10002000036). (注：eと λからdを求める方法は，�この例のように数が大きいと工夫する必要があることがわかる。. ��その方法は後述する。）.

(65) RSA:鍵の生成（復号の説明の準備）� • 大きな素数p, qを決める：秘密. • λをp-1とq-1の最小公倍数とする．. �[あるa,bが存在して，λ＝a（p-1）, λ＝b（q-1）]...①. • eをλと互いに素な数として決める。このときed = 1 (mod λ)なるdがもとまる。. [あるKが存在して，ed= Kλ+1 ]...②. n(= pq)とeを公開する。�.

(66) RSA:鍵の性質�. �. • 任意の整数m, と任意の整数Kについて，�� mKλ＋1=m (mod n). 証明. pとqが素数であり、n＝pqであり，. λがp-1とq-1の最小公倍数（①）なので，（☆☆）を用いると，�任意のKについて，. ��mKλ＋1=m (mod n) ... ③.

(67) RSA: 送信・受信� c=me(mod n)で暗号化しcを送る��... ④. m'=cd(mod n)で復号しm'を得る��... ⑤�.

(68) RSA暗号:通信ができるわけ� m'. =cd(mod n). =med(mod n) . =m(Kλ+1)(mod n). = m (mod n) . ��. ←⑤. ←④. ←②. ←③.

(69) RSA:鍵の生成の難しいところ� • λは大きな数（素数ではない。。）. • λと互いに素なeを求める. • ed = 1 (mod λ)を満たすdを求める. 例：1= 20003×2564628215 (mod 10002000036). • λは大きな数. そのような数dは存在するのか。。。. eからdを、どうやってもとめればよいのか。。。. ��λが大きいと，�順番にdを探すことは不可能。。.

(70) RSA:鍵の生成の難しいところ逆数を求めるところ� • ed = 1 (mod λ)を満たすdを求める. 例：1= 20003×d (mod 10002000036)となるdを求める。. つまり 20003×dを10002000036で割った商を-βとして，�そのときのあまりが1になるようなdを求める。. • 1=20003×d + 10002000036×β. を満たす，�整数dと整数βを求めたい。. 「整数」という条件は難しい条件である。.

(71) 20003逆数を求める方針�. �. 目標：「整数dと整数βで，. ��1=20003×d + 10002000036×βとしたい。」. γ（d, β)�＝20003×d+10002000036×βとして，. (d, γ，�β)の三次元の格子点（座標が整数の点）を対象に演算をして，�格子点であることを保証しつつ，γ ＝1となる点を求める。. (1, 20003, 0)と(0,10002000036,1)からスタートする。.

(72) ユークリッドの互除法� • お互いに割り算をして，余りをとっていく。. • 最大公約数を求めることができる。. – 例を板書(次のスライド）. . .

(73) u=7, v=5� 7, 5 -> �商は1、. あまりは7 – 1 ×5�= 2. 5, 2 -> 商は2. あまりは5 – 2 ×2�= 1. 2, 1 ��-> 商は2. あまりは2-2× 2 = 0なので、その前の数字1. GCD(7, 5)=1.

(74) ユークリッド互除法の操作の準備� dとλで定まる平面で，（α，�αd + βλ , β)の平面は原点を通るので、. 平面上の2点の位置ベクトルp, qに対し、任意の実数tについて、p-tqで表される点も、同じ平面にある。.

(75) ユークリッド互除法の操作の準備� 要素が整数の2つのベクトルp=(px，�py, pz), q=(qx,qy,qz)があり、これが（α，�αd + βλ , β)の平面2点の位置ベクトルであるとする。. いま、tをpyをqyで割ったときの整数の商であるとすると、r = p – t qで定まるベクトルr =(rx, ry, rz)とする。. ◯rx, ry, rzは整数. ◯ryが0でないときGCD（py, qy）=GCD(qy, ry). ◯rは同じ平面上にある点の位置ベクトル.

(76) ユークリッド互除法の拡張� dとλから定まる平面で，�（α，�αd + βλ , β)の関係のある3次元空間の平面において，(1, d, 0)と（0,λ,1)からユークリッドの互除法を実行する。（板書）. ユークリッドの互除法と同じ動作をして、α，β を更新していく。. 二つ整数u, vに対し，ある整数α，βが存在して. αd + βλ = GCD(d, λ)となることが示せる。.

(77) u=7, v=5, (α，�7α＋5β, β)� (1, 7, 0), (0, 5, 1) -> �7÷5は1、あまりがある. 次の点は (1, 2, -1)=(1, 7, 0) – 1× (0, 5, 1). (0, 5, 1), (1, 2 , -1) -> 5÷2は2、あまりがある. �次の点は(-2, 1, 3) = (0, 5, 1) – 2 ×(1, 2, -1). (1, 2, -1), (-2, 1, 3) ��-> 割り切れる. �目的地(-2, 1, 3)に到達、. 1=GCD(7, 5), (-2) ×7 + 3×5 = 1.

(78) (α，�7α＋5β, β)の平面内 α，βは整数� (1, 7, 0), (0, 5, 1) より、操作を開始、. (1, 7, 0), (0, 5, 1) -> (1, 2, -1). (0, 5, 1), (1, 2, -1) -> (-2, 1, 3) . (-2, 1, 3) は目的地，なぜなら，1 = GCD(7, 5). このとき， 7×(-2) +5× (3) = 1. つまり， 7×(-2) = 1 (mod 5).

(79) (α，�3α＋4β, β)の平面内 α，βは整数� (0, 4, 1) , (1, 3, 0) より、操作を開始、. (0, 4, 1), (1, 3, 0) -> (-1, 1, 1). (-1, 1, 1) は目的地，なぜなら，1 = GCD(3, 4). このとき， 3×(-1) +1× (4) = 1. つまり， 3×(-1) = 1 (mod 4), -1 = 3 (mod 4).

(80) RSA:鍵の生成� • • • • . 大きな素数p, qを決める：�p=100003, q=100019. λをp-1とq-1の公倍数 (10002000036)とする．. eをλと互いに素な数: 20003とする．. ed(mod λ)=1となるdをもとめ，d:2564628215とする．. 1= 20003×2564628215 (mod 10002000036). • n(= pq=10002200057)とe（=20003)を公開する。�.

(81) ☆RSA:まとめ（転記）�. �. 鍵の生成. • 大きな素数p, qを決める：秘密. • λをp-1とq-1の最小公倍数とする．. • eをλと互いに素な数として決める。このとき ed =1(mod λ)なるdがもとまる。. n(= pq)とeを公開する。. 送信：c=me(mod n)で暗号化しcを送る��. 受信：m'=cd(mod n)で復号しm'を得る�.

(82)