1. No category

公開鍵暗号�RSAについて
3年授業「情報ネットワーク」
授業スライドより抜粋�
豊橋技術科学大学
情報・知能工学系
梅村恭司
2014-07-02 �
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)�が成立する：デモ�
素朴な疑問�
–  10002200057(公開）, 20003（公開）,
2564628215（秘密）
•  ベキ乗演算で暗号化
•  ベキ乗演算で復号�（計算は遅くないか）�
計算の複雑さとO(N)
コンピュータの演算速度は人間に比べると高速
であるが、無限の速度をもっているわけではな
い。計算時間が、入力の引数の値の指数関数
となるようなものは、高速のコンピュータでも実
際的には計算できない。
O（N ）は、与えられたNに比例する量で増えるこ
とを注目し、定数倍は議論しないときに用いら
れる形式である。�
掛け算の計算�
•  乗算：a *�x�= yを計算するプログラム
y = 0;
for (i = 0 ; i <x ; i++) { y = y ＋ a; }
O(x)の加算演算：
xが10の10乗くらいであると計算は大変
こんな計算は普通しない。
€
掛け算の計算は10の10乗でも問題
なく実行できる。�
•  掛け算：a *�x�= y
たとえば、x＝1024なら、
y = a;
for (i = 0 ; i <10 ; i++) { y = y ＋ y; }
k
a
× 2
を計算しておき，xを2進数で表現して、bitが立っている
桁のkの
k
a
× 2
の加算で計算する。O(log(x))の加算の回数
10の10乗のベキ乗の計算も掛け算
と同様�
•  ベキ乗、a x = y (mod p)
たとえば、x＝1024なら、
y = a;
for (i = 0 ; i <10 ; i++) { y = y * y; }
a
2k
を計算しておくxを2進数で表現して、bitが立っている桁
のkの
€
a
2k
の積で計算する。O(log(x))のかけ算の回数
そして�pの剰余で計算するので，桁数も大きくない。
高速なベキ乗計算の定義�
public static int power(int p, int a, int x, int n, int r) {　// return (r * (n ^ x ) mod p) return ((x == 0)?
r:
power( p, a, x/2, (n*n) % p,
(r * (((x&1)==0)? 1: n) % p)　) );
}
素朴な疑問へ回答�
–  10002200057(公開）, 20003（公開）,
2564628215（秘密）
•  ベキ乗演算で暗号化
•  ベキ乗演算で復号�
やり方を工夫すれば、ベキ乗演算は高速
素朴な疑問�
–  10002200057(公開）, 20003（公開）,
2564628215（秘密）
•  ベキ乗演算で暗号化
•  ベキ乗演算で復号�
どうして、通信できるのか。。。。
�説明には有限体の知識が必要�
剰余系�
•  12 = 22 (mod 10)
•  数を5で割ったあまりで比較すれば，12と22
は同じ
•  (mod 10)は比較の方法を記述したもの
–  「等しい」という関係を修飾している。
16
剰余系�
数字の比較のときに、かならずあまりで比較する
ことにする。
足し算／掛け算をして比較するときには，�計算す
る前にあまりをとったとしても，�比較結果はお
なじ
19＋12 = 1 (mod 10)と4+2=1 (mod 10)
19×12 = 8 (mod 10)と4×2=8 (mod 10)
17
剰余系�
数字の比較のときに、かならずあまりで比較する
ことにする。
両辺に同じ数を加算，減算，�乗算することができ
る。
a=4 (mod 10) ならば，�a+2 = 4+2 (mod 10)
a=4 (mod 10) ならば，�a-2 = 4-2 (mod 10)
a=4 (mod 10) ならば，�a×2�= 4×2 (mod 10)
18
剰余系�
数字の比較のときに、かならずあまりで比較する
ことにする。
同じ数で割り算をすると等しくなるとは限らない。
18 = 8 (mod 10) だが， 18/3 ≠�3/3 (mod 10)
19
整数をあまりでグループ分けする。
グループに名前をつける。
�
�「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�
20
グループでの足し算と掛け算表�
+�
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�
21
「負の数」と「逆数」�
この演算表では，
�−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�
22
有限体�
「体」とは、数の集合と演算の組合わさったもの
のである，ある性質をもつものの名前である。
「体」の重要な性質の一つは，ある数の乗算に
逆演算となる数が存在する数が、0以外には
存在することである。逆演算となる数があるこ
とが復号で役立つ。
有限の集合での「乗算」の体系に「逆数」が存在
するのは，面白い性質。
23
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)�が成立する。�
24
フェルマーの小定理 •  pが素数のとき，ap-1=1 (mod p)
����ただし，�a=1, 2, ... p-1
•  どのような定理か
aがどれであっても，aをp−1回掛ける（ベキ乗す
る）と1になることが運命付けられている。
p=5のときを計算してみよう。
25
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)
26
観測：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�
観測：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�
フェルマーの小定理の証明の
準備（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の倍数である
ことになり、仮定と矛盾する。
フェルマーの小定理の証明の
準備 （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�
フェルマーの小定理の証明の
準備 （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)となる。
フェルマーの小定理の証明の
準備(3) pは素数とする。
aは，1からp-1まで整数とする。
Sは1からp-1までの整数の集合とする。
T(a)={m | n∈S, m=na (mod p) }なる集合T(a)
を考える。すると、|T(a) |= |S| = p-1
証明：
nごとに対応するmは異なるので，T(a)の要素
の個数はSと同じp-1になる。
フェルマーの小定理の証明の
準備(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=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�
フェルマーの小定理の証明の
準備(5) ×�0� 0�0� 1�0� 2�0�
1� 0� 1� 2�
pを素数とする。
2� 0� 2� 4�
3� 0� 3� 1�
a, nは，1からp-1まで整数とする。
4� 0� 4� 3�
Sは1からp-1までの整数の集合とする。
任意のaに対しあるnが存在して1 = na (mod p)
証明
��T(a)={m | n∈S, m=na (mod p) }とする。
� 1∈S，より1∈T(a), よって，∃n, 1=na (mod p)
3�
4�
0�
0�
3�
4�
1�
3�
4�
2�
2�
1�
フェルマーの定理（実演） •  pが素数のとき ap-1=1 (mod p)
aは�1からp-1まで，�どれでも成立する。�
（p=100003�で実験）
�
35
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�
。�
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}
∏n
pが素数なので、b������=1となるbが存在するので，
n∈S
p −1
それを右から掛けると，�
1 = a (mod p)
フェルマーの小定理の系（☆）
•  pが素数、λがp-1の倍数のとき，aλ＋1=a (mod p)
����注意：aが任意の整数で成立
�������aの制限がないので，使いやすい。
また，記憶しやすい。
�
38
ベキ乗の計算�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乗もおなじようにもとにもどる。
39
フェルマーの小定理の系（☆）の
証明
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)
40
�
中国人の剰余定理
�
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)�
p(=2)�
0�
1�
2�
3�
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についてaKλ+1=a (mod pq)
45
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)
二つの素数に関わる性質の証明
•  pとqが素数のとき λをp-1とq-1の 最小公倍
数とすると，任意の整数Kについて
���aKλ+1=a (mod pq)
証明：b=aKλ+1とする。�
�Kλはpの倍数であるので（☆）より
����������������������������������b=aKλ+1=a (mod p）
Kλはqの倍数でもあるので，�b=aKλ+1=a (mod q）
pとqは互いに素であるので，中国人の剰余定理
47
により，�b=aKλ+1=a (mod pq）
�
RSA暗号�
•  フェルマーの定理
•  ユークリッドの互除法と拡張
これらをつかって，�2つの大きな素数から
�上手にn , e, dを生成する
�
n=10002200057(公開）, e=20003（公開）,
d=2564628215（秘密）
e: encode, d:decode
48
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
暗号化�
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)
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）]...①
•  eをλと互いに素な数として決める。このときed =
1 (mod λ)なるdがもとまる。
[あるKが存在して，ed= Kλ+1 ]...②
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=me(mod n)で暗号化しcを送る����... ④
m'=cd(mod n)で復号しm'を得る��... ⑤�
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=(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は同じ平面上にある点の位置ベクトル
ユークリッド互除法の拡張�
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=me(mod n)で暗号化しcを送る���
受信：m'=cd(mod n)で復号しm'を得る�