公開鍵暗号 RSA について 3 年授業 情報ネットワーク 授業スライドより抜粋 豊橋技術科学大学情報 知能工学系梅村恭司 2015-06-24 Copyright 2014 Kyoji Umemura (http://www.ss.cs.tut.ac.jp/) 出典を明らかにしていただければ 自由に授業 / セミナー等で使っていただいて結構です
これからのスライドは下記を参考 に,Java でプログラミングしながら, 作成しました 岡本栄司著, 暗号理論入門 [ 第 2 版 ] 共立出版株式会社
RSA 暗号とネットワーク 暗号化と復号の鍵を別にして, かつ, 暗号化の鍵を公開できると便利 計算量という壁を使って, 上記を実現したものの代表が RSA 暗号 これを理解するには, 整数論の知識が必要 : ある整数で割った余りで等しい整数の体系 を扱う
Java の BigInteger クラス import java.math.biginteger; x = new BigInteger("1234567"); System.out.println(x.toString());
剰余系 17 = 22 (mod 5) 数を 5 で割ったあまりで比較すれば,17 と 22 は同じ (mod 5) は比較の方法を記述 あまりをとる演算子ではない
BigPower のデモ (mod n) で, aのx 乗を計算するプログラム % java BigPower 1000 2 9 1000 2 9 512 1000 2 10 1000 2 10 24
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) が成立する デモ
RSA:n = 10, e = 3, d = 3 暗号化 ( 板書 ) 1 3 = 1 (mod 10) 2 3 = 8 (mod 10) 3 3 = 7 (mod 10) 4 3 = 4 (mod 10) 5 3 = 5 (mod 10) 6 3 = 6 (mod 10) 7 3 = 3 (mod 10) 8 3 = 2 (mod 10) 9 3 = 9 (mod 10)
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)
素朴な疑問 10002200057( 公開 ), 20003( 公開 ), 2564628215( 秘密 ) ベキ乗演算で暗号化 ベキ乗演算で復号 どうして 通信できるのか 説明には有限体の知識が必要
剰余系 12 = 22 (mod 10) 数を 10 で割ったあまりで比較すれば,12 と 22 は同じ (mod 10) は比較の方法を記述したもの 等しい という関係を修飾している 11
a = b (mod n) n で割った余りを問題にするならば,a と b は等しい 直感的にわからなかったら,n=10 とする これは, 整数の一番下の桁で整数を比較することになる
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) 推移律
a = b (mod n) n で割った余りを問題にするならば,a と b は等しい 整数は,n 個のグループに分類されるが, そのグループのなまえに,0 から n-1 までの整数を使う これは, グループの名前であることに注意する必要がある
加算 a=b (mod n) ならば, z 整数, a+z = b+z (mod n) 直感的にわからなかったら,n=10 とする これは, 整数の一番下の桁で整数を比較することになる グループの名前を求めるには, 通常の加算をして, 下の桁だけを使うことでよい
減算 a=b (mod n) ならば, z 整数, a-z = b-z (mod n) 直感的にわからなかったら,n=10 とする これは, 整数の一番下の桁で整数を比較することになる グループの名前を求めるには, 負にならないように 10 を加算することをして, 一番したの桁を使うことでよい
乗算 a=b (mod n) ならば, z 整数, z a = z b (mod n) 直感的にわからなかったら,n=10 とする これは, 整数の一番下の桁で整数を比較することになる グループの名前を求めるには, 通常の乗算をして, 一番下の桁だけを使うことでよい
逆数 (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)
逆数 (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は存在しない
逆数 : (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)
逆数 (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 は存在しない
逆数 (mod 素数 p) n=1, 2,..., p-1について, x = n -1 (mod p) となる,xがある 注意,n 0である x = 0-1 (mod p) を満たすxは存在しない
割り算 (mod 素数 p) n=1, 2,..., p-1 について, x = n -1 (mod p) となる,x がある y/n は,y n -1 と考える ( 掛け算の逆演算 ) すると,0 以外の数で割り算した結果が存在する ( 整数はみたさないが, 有理数や実数が満たす性質 : 集合と加算と乗算が 体 である )
整数をあまりでグループ分けする グループに名前をつける 5で割ったあまりが0の整数 を "0" と書くことにする "1", "2", "3", "4" も同様, つまり, "1" は,{ 1, 6, 11, 16,... } のグループのこと, グループは5つある 演算は表にできる + 0 1 2 3 4 0 0 1 2 3 4 1 1 2 3 4 0 2 2 3 4 0 1 3 3 4 0 1 2 4 4 0 1 2 3 0 1 2 3 4 0 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 24
グループでの足し算と掛け算表 + 0 1 2 3 4 0 0 1 2 3 4 1 1 2 3 4 0 2 2 3 4 0 1 3 3 4 0 1 2 4 4 0 1 2 3 0 1 2 3 4 0 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 25
負の数 と 逆数 この演算表では, 2 は 3 と考えると考えることができる 2 1 は, 3 と考えることができる + 0 1 2 3 4 0 0 1 2 3 4 1 1 2 3 4 0 2 2 3 4 0 1 3 3 4 0 1 2 4 4 0 1 2 3 0 1 2 3 4 0 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 26
有限体 体 とは 数の集合と演算の組合わさったもののである, ある性質をもつものの名前である 体 の重要な性質の一つは, ある数の乗算に逆演算となる数が存在する数が 0 以外には存在することである 逆演算となる数があることが復号で役立つ 有限の集合での 乗算 の体系に 逆数 が存在するのは, 面白い性質 27
RSA 暗号の例 ( 再度 ) 大きな素数 2 つ ( 秘密 ) から n と鍵を二つ生成する e: encode_key, d: decode_key n=10002200057( 公開 ), e=20003( 公開 ), d=2564628215( 秘密 ) ベキ乗演算で暗号化 c=m e (mod n) ベキ乗演算で復号 m'=c d (mod n) つまり m'=c d =m ed (mod n) このとき, m'=m (mod n) が成立する 28
フェルマーの小定理 pが素数のとき ap-1=1 (mod p) ただし a=1, 2,... p-1 どのような定理か aがどれであっても aをp 1回掛ける ベキ乗す る と1になることが運命付けられている p=5のときを計算してみよう 29
p(=5) のときの フェルマーの小定理の確認 p(=5) が素数のとき,a p-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なので 0 p-1 1 (mod p) 30
観測 :p=5 では na の集合と a の集合に 1 対 1 対応が存在する p(=5) は素数 a と n は,1 から p-1 まで整数とする S は 1 から p-1 までの整数の集合とする 任意の a に対し n と an に (mod p) での 1 対 1 対応が存在する 0 1 2 3 4 0 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
観測 :p=5では, 0でないaには, 逆数が存在存在する p(=5) は素数 aは,1からp-1まで整数とする Sは1からp-1までの整数の集合とする 任意のaに対して, an=1 (mod p) となる nが存在する 0 1 2 3 4 0 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
フェルマーの小定理の証明の p は素数とする 準備 (1) 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 の倍数であることになり 仮定と矛盾する
フェルマーの小定理の証明の準備 (2) pは素数とする aは,1 以上 p-1 以下の整数とする x yは1 以上 p-1 以下の異なる整数とする すると ax ay (mod p) つまり 0でないx,yで異なるx, y をa 倍した結果をpで割った余ま りは異なるということを意味している 0 1 2 3 4 0 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
フェルマーの小定理の証明の準備 (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) となる
フェルマーの小定理の証明の p は素数とする 準備 (3) 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 になる
フェルマーの小定理の証明の 準備 (4) pは素数とする aは,1からp-1まで整数とする 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 0 1 2 3 4 0 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
フェルマーの小定理の証明の 準備 (5) pを素数とする a, nは,1からp-1まで整数とする S は 1 から p-1 までの整数の集合とする 0 1 2 3 4 0 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 任意の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)
フェルマーの定理 ( 実演 ) pが素数のとき a p-1 =1 (mod p) aは 1からp-1まで, どれでも成立する (p=100003 で実験) 39
a の集合と anの集合が等しい 0を除いて全部掛け合わせてみる 掛け合わせる対象の集合をSとする S={1,2,..., p-1} 0 1 2 3 4 0 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
n と a n が S 上で 1 対 1 に対応している 全部掛け合わせる n = an(mod p) n T (a) n S n = a p 1 n(mod p) n T (a) n S n = a p 1 n(mod p) n S T(a)=S={1,2,..., p-1} n S n S pが素数なので b n =1 (mod p) となるbが存在するので, それを右から掛けると, 1 = a p 1 (mod p)
フェルマーの小定理の系 pが素数 λがp-1の倍数のとき aλ 1=a (mod p) 注意 aが任意の整数で成立 aの制限がないので 使いやすい また 記憶しやすい 42
ベキ乗の計算 p の 5 乗 (mod 5) p(=5) が素数のとき,a p =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
フェルマーの小定理の系 ( ) の 証明 pが素数 λがp-1の倍数のとき,a λ+1 =a (mod p) 証明 : ある整数 kをaをpで割ったときの商とする (1)a=kp のとき, 明らかに a λ+1 =k λ+1 p λ+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 =b K(p 1)+1 =(b (p 1) ) K b=1 K b (mod p) 一方,a=b (mod p) よって, a λ+1 =a (mod p) 44
中国人の剰余定理 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桁目がわかる
中国人の剰余定理 pとqが互いに素でないときは n=pq として, ある数 x, y が x=y (mod p) かつ,x=y (mod q) であっても x=y (mod n) とはいえない q(=4) 0 1 2 3 p(=2) 0 0, 4-2, 6-1 - 1, 5-3, 7 n(=8)
中国人の剰余定理 ( 証明の準備 ) 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) となる
中国人の剰余定理 / 証明 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)
二つの素数に関わる性質 pとqが素数のとき λをp-1とq-1の最小公倍 数とすると 任意の整数K aについてakλ+1=a (mod pq) 49
p(=2) と q(=5) が素数のとき λ を p-1 と q-1 の倍数とすると, a λ+1 =a (mod pq) 0 3 = 0 (mod 10) 1 3 = 1 (mod 10) 2 3 = 8 (mod 10) 3 3 = 7 (mod 10) 4 3 = 4 (mod 10) 5 3 = 5 (mod 10) 6 3 = 6 (mod 10) 7 3 = 3 (mod 10) 8 3 = 2 (mod 10) 9 3 = 9 (mod 10) 0 4 = 0 (mod 10) 1 4 = 1 (mod 10) 2 4 = 6 (mod 10) 3 4 = 1 (mod 10) 4 4 = 6 (mod 10) 5 4 = 5 (mod 10) 6 4 = 6 (mod 10) 7 4 = 1 (mod 10) 8 4 = 6 (mod 10) 9 4 = 1 (mod 10) 0 5 = 0 (mod 10) 1 5 = 1 (mod 10) 2 5 = 2 (mod 10) 3 5 = 3 (mod 10) 4 5 = 4(mod 10) 5 5 = 5 (mod 10) 6 5 = 6 (mod 10) 7 5 = 7 (mod 10) 8 5 = 8 (mod 10) 9 5 = 9 (mod 10)
二つの素数に関わる性質の証明 p と q が素数のとき λ を p-1 と q-1 の最小公倍数とすると, 任意の整数 K について a Kλ+1 =a (mod pq) 証明 :b=a Kλ+1 とする Kλ は p-1 の倍数であるので ( ) より b=a Kλ+1 =a (mod p) Kλ は q-1 の倍数でもあるので, b=a Kλ+1 =a (mod q) pとqは互いに素であるので, 中国人の剰余定理に 51 より, b=a Kλ+1 =a (mod pq)
RSA 暗号 フェルマーの定理 ユークリッドの互除法と拡張これらをつかって, 2つの大きな素数から 上手にn, e, dを生成する n=10002200057( 公開 ), e=20003( 公開 ), d=2564628215( 秘密 ) e: encode, d:decode 52
RSA:鍵の生成 大きな素数p, qを決める λをp-1とq-1の最小公倍数とする eをλと互いに素な数として決める ed = 1(mod λ)となる dを求める n(= pq)とeを公開する (他は秘密とする これから 具体的に計算してみる
RSA: 鍵の生成 素数 p, q を決める : p=2, q=5
RSA: 鍵の生成 素数 p, q を決める : p=2, q=5 λ を p-1 と q-1 の最小公倍数 (= 4 ) とする.
RSA: 鍵の生成 素数 p, qを決める : p=2, q=5 λをp-1とq-1の最小公倍数 (=4) とする. eをλと互いに素な数 : たとえば3とする. ( 互いに素 : 最大公約数が 1 であること )
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) 注 : ここでは順番にテストしてもとめるが, 効率のよい方法がある
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
RSA:n = 10, e = 3, d = 3 暗号化 1 3 = 1 (mod 10) 2 3 = 8 (mod 10) 3 3 = 7 (mod 10) 4 3 = 4 (mod 10) 5 3 = 5 (mod 10) 6 3 = 6 (mod 10) 7 3 = 3 (mod 10) 8 3 = 2 (mod 10) 9 3 = 9 (mod 10)
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)
RSA: 鍵の生成 大きな素数 p, q を決める : p=100003, q=100019
RSA: 鍵の生成 大きな素数 p, q を決める : p=100003, q=100019 λ を p-1 と q-1 の公倍数 (10002000036) とする.
RSA: 鍵の生成 大きな素数 p, qを決める : p=100003, q=100019 λをp-1とq-1の公倍数 (10002000036) とする. eをλと互いに素な数 : 20003とする. ( 互いに素 : 最大公約数が 1 であること )
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 を求める方法は, この例のように数が大きいと工夫する必要があることがわかる その方法は後述する )
RSA: 鍵の生成 ( 復号の説明の準備 ) 大きな素数 p, q を決める : 秘密 λ を p-1 と q-1 の最小公倍数とする. [ ある a,b が存在して,λ=a(p-1), λ=b(q-1)]...1 e を λ と互いに素な数として決める このとき ed = 1 (mod λ) なる d がもとまる [ ある K が存在して,ed= Kλ+1 ]...2 n(= pq) と e を公開する
RSA:鍵の性質 任意の整数m, と任意の整数Kについて mkλ 1=m (mod n) 証明 pとqが素数であり n pqであり λがp-1とq-1の最小公倍数 ① なので を 用いると 任意のKについて mkλ 1=m (mod n)... ③
RSA: 送信 受信 c=m e (mod n) で暗号化し c を送る... 4 m'=c d (mod n) で復号し m' を得る... 5
RSA暗号:通信ができるわけ m' =cd(mod n) =med(mod n) =m(kλ+1)(mod n) = m (mod n) ⑤ ④ ② ③
RSA: 鍵の生成の難しいところ λは大きな数 ( 素数ではない ) λと互いに素なeを求める ed = 1 (mod λ) を満たすdを求める 例 :1= 20003 2564628215 (mod 10002000036) λは大きな数そのような数 dは存在するのか eからdを どうやってもとめればよいのか λが大きいと, 順番にdを探すことは不可能
RSA: 鍵の生成の難しいところ 逆数を求めるところ ed = 1 (mod λ) を満たす d を求める 例 :1= 20003 d (mod 10002000036) となる d を求める つまり 20003 d を 10002000036 で割った商を -β として, そのときのあまりが 1 になるような d を求める 1=20003 d + 10002000036 β を満たす, 整数 d と整数 β を求めたい 整数 という条件は難しい条件である
20003 逆数を求める方針 目標 : 整数 d と整数 β で, 1=20003 d + 10002000036 β としたい γ(d, β) =20003 d+10002000036 β として, (d, γ, β) の三次元の格子点 ( 座標が整数の点 ) を対象に演算をして, 格子点であることを保証しつつ,γ =1 となる点を求める (1, 20003, 0) と (0,10002000036,1) からスタートする
ユークリッドの互除法 お互いに割り算をして, 余りをとっていく 最大公約数を求めることができる 例を板書 ( 次のスライド )
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
ユークリッド互除法の 操作の準備 d と λ で定まる平面で,(α, αd + βλ, β) の平面は原点を通るので 平面上の 2 点の位置ベクトル p, q に対し 任意の実数 t について p-tq で表される点も 同じ平面にある
ユークリッド互除法の 操作の準備 要素が整数の 2 つのベクトル p=(p x, p y, p z ), q=(q x,q y,q z ) があり これが (α, αd + βλ, β) の平面 2 点の位置ベクトルであるとする いま t を p y を q y で割ったときの整数の商であるとすると r = p t q で定まるベクトル r =(r x, r y, r z ) とする r x, r y, r z は整数 r y が 0 でないとき GCD(p y, q y )=GCD(q y, r y ) r は同じ平面上にある点の位置ベクトル
ユークリッド互除法の拡張 d と λ から定まる平面で, (α, αd + βλ, β) の関係のある 3 次元空間の平面において,(1, d, 0) と (0,λ,1) からユークリッドの互除法を実行する ( 板書 ) ユークリッドの互除法と同じ動作をして α,β を更新していく 二つ整数 u, v に対し, ある整数 α,β が存在して αd + βλ = GCD(d, λ) となることが示せる
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
(α, 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)
(α, 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)
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) を公開する
RSA: まとめ ( 転記 ) 鍵の生成 大きな素数 p, q を決める : 秘密 λ を p-1 と q-1 の最小公倍数とする. e を λ と互いに素な数として決める このとき ed =1(mod λ) なる d がもとまる n(= pq) と e を公開する 送信 :c=m e (mod n) で暗号化し c を送る 受信 :m'=c d (mod n) で復号し m' を得る