Literacy 2 Mathematica Mathematica 3 Hiroshi Toyoizumi Univ. of Aizu REFERENCES [1] C.P Williams [2] [3] 1 Literacy 2 Mathematica Ma

(1)

1

Mathematica 3

Hiroshi Toyoizumi Univ. of Aizu toyo@u-aizu.ac.jp REFERENCES： [1] 量子コンピューティング C.P Williams [2] ハンドアウト佐川先生 [3] コンピュータ理工学のすすめ講義資料豊泉 Literacy 2 Mathematica

今日のテーマ

① Mathematicaを使って、公開鍵暗号方式による暗号

化をやってみよう。

② Mathematicaを使って、公開鍵暗号方式による暗号

をクラックしてみよう。

(2)

3

暗号技術によるセキュリティ強

化

① 暗号化：知られたくない重要な情報は

暗号化する。

② 認証：自分が誰かを証明する。

③ 公開鍵暗号系

④ PKI：Public Key Infrustructure

Literacy 2 Mathematica

非対称暗号鍵方式

（公開鍵暗号方式）

(3)

5

実際の暗号通信

(4)

7

暗号化の方式

非対称鍵

① RSA

最も有名で最も広く使用されているアルゴリズム。アルゴリズムの名前は、3人の開発者のRonald Rivest氏、Adi Shamir氏、Leonald Adleman氏の頭文字を取って付けられた。米国RSAセキュリティ社が特許を持っていたが、2000年9月特許の期限切れを迎えた。暗号、電子署名、鍵配送の機能を持つ ② DSA アメリカの電子署名標準アルゴリズム。電子署名のみの機能を持ち、暗号化の機能は持っていない ③ Diffie-Hellman

Whitfield Diffie氏とMartin E. Hellman氏によって開発されたアルゴリズムで、鍵配送の機能のみ持っている。ちなみに「公開鍵暗号」は Diffie氏によって考案され、1976年に Hellman氏との共同論文「New Directions in Cryptography」で発表された。RSA社の3人は、この論文を読んで感嘆し、RSAの開発を始めた Literacy 2 Mathematica

Mathematicaの整数論関数

① Mod

② GCD

③ FactorInteger

④ Divisors

⑤ Prime

⑥ PrimeQ

⑦ ExtendGCD

⑧ EulerPhi

(5)

9

CharacterCode

① ToCharacterCode["string"] gives a list of

the integer codes corresponding to the

characters in a string.

In[1]:= ToCharacterCode["Everything is an expression."] Out[1]={69,118,101,114,121,116,104,105,110,103,32,105, 115,32,97,110,32,101,120,112,114,101,115,115,105,1 11,110,46} In[2]:= FromCharacterCode[%] Out[2]= Everything is an expression.

Mod

① Mod[m, n]

gives the

remainder on

division of m

by n.

(6)

11

GCD

① GCD

gives the

greatest

common

divisor of

the

integers

FactorInteger[n]

① FactorInteger

[n] gives a list

of the prime

factors of the

integer n,

together

with their

exponents.

(7)

13

Divisors[n]

① Divisors[n]

gives a list of

the integers

that divide n.

Prime

① Prime[n]

gives the

n-th prime

number.

(8)

15

PrimeQ[expr]

① PrimeQ[ex

pr] yields

True if expr

is a prime

number,

and yields

False

otherwise.n

ExtendedGCD

① The first element in the output from

ExtendedGCD[n, m] is the greatest common

divisor of the integers n and m.

In[1]:={g,{r,s}}=ExtendedGCD[n=45,m=36] Out[1]= {9,{1,-1}}

In[2]:= GCD[45,36] Out[2]= 9

② The second element is a pair of integers. The

linear combination of n and m with these as

coefficients gives the gcd.

In[3]:= nr+ms Out[3]= 9

(9)

17

互いに素な場合

① These two numbers are relatively prime.

In[4]:= {g, {r, s}} = ExtendedGCD[2^100 + 3, 3^50 + 8]) Out[4]={1,{62013782892351778750374,

-109502757290992473821761130785}}

② Therefore this linear combination gives

1.

In[5]:= (2^100 + 3) r + (3^50 + 8) s Out[5]= 1

EulerPhi[n]

① EulerPhi[n] gives the Euler totient function φ(n) . ② EulerPhi[n] gives the number of positive integers less

than or equal to n which are relatively prime to n. Up to 10 there are four numbers relatively prime to 10. ① In[1]:= EulerPhi[10]

(10)

19

Eulerの定理

自然数ｎと整数aで、

GCD(a,n)=1

のとき



a＾φ(n) = 1 mod n

Eulerの定理の例

In[1]:=GCD[5, 17] Out[1]=1 In[2]:=EulerPhi[17] Out[2]=16 In[3]:=Mod[5^EulerPhi[17], 17] Out[3]=1 In[5]:=Mod[10^EulerPhi[17], 17] Out[5]=1

(11)

21

RSA暗号方式

① ２つの鍵（公開鍵・秘密鍵）をつかう。

② 暗号文の解読が困難である。

③ 公開鍵から秘密鍵を推測することが困難で

ある。

④ キーポイント：大きな数の因数分解が困難

である。

非対称暗号鍵方式

（公開鍵暗号方式）

(12)

23

公開鍵と秘密鍵の作り方

（１）

e:一つ目の鍵 ① 二つ大きな素数を（ｐ、ｑ）を選ぶ。  p=5, q=17 In[2]:=PrimeQ[5] Out[2]=True In[3]:=PrimeQ[17] Out[3]=True ② pとｑの積ｎを計算する。  n = p q = 85 ③ φ(n)=(p-1)(q-1)を計算する  (p-1)(q-1) = 64 ④ (p-1)(q-1)と互いに素な整数eをみつける  e = 3 Literacy 2 Mathematica

公開鍵と秘密鍵の作り方

（２）

ｄ:二つ目の鍵

①

e d = 1 mod (p-1)(q-1)となるように

dを選ぶ。



d=43と選ぶと



e d = 343 = 129 = 64 2 +1 = 1 mod 64

このようなｄを選ぶアルゴリズムは後述

(13)

25

ｄの選び方

① e d = 1 mod (p-1)(q-1)となるｄは以下の

ように選ぶことができる。

e d = 1- k (p-1)(q-1)

e d +k (p-1)(q-1) = 1

① これを満たすｄはExtendedGCDによって

求めることができる。

② {1,{d,k}}=ExtendedGCD[e, (p-1)(q-1)]

③ dには、(p-1)(q-1)を法とする不定性がある

ので、適当に、 (p-1)(q-1)のα倍を足して調

整して、ｄを正に選ぶ。

ｄの選び方の例

e = 3, (p-1)(q-1)=64のとき

In[7]:=｛g, {d, k}} = ExtendedGCD[3, 64]

Out[7]={1,{-21,1}}

In[8]:=d + 64

Out[8]=43

(14)

27

暗号の通信の準備

① Bobが公開暗号鍵として(e,n)を公開

する。

② AliceはBobの公開暗号鍵を入手す

る。

Aliceの暗号文の作り方

①

_{Mを暗号にしたい文章とする。（但しＭ＜ｎ）}

②

_{Bobの公開鍵（e,n)を使い、暗号文Cを作る。}

C = M^e mod n

例 (e,n) = (3, 85), M=77

In[1]:=Mod[77^3, 85] Out[1]=83 したがって、暗号文Cは８３となる。

(15)

29

Bobの暗号文の解読の仕方

① Aliceから暗号文Cを受け取る ② 自分だけが知っている秘密鍵dを使って、暗号文を解読する。 C^d = M^(ed) mod n = M^(1+k (p-1)(q-1)) mod pq = M*{M^k}^(p-1)(q-1) mod pq  Mがpまたはqの倍数でない場合はEulerの定理を使い = M mod pq  Mがｐの倍数のときには、適当な自然数ｊが存在して、M=jpとなり、 = j {j^k(p-1)}^q mod q ここで、Eulerの定理を使うと = j mod q = M mod pq Mがｑの倍数のときにも同様。いずれの場合も C^d=M mod n となることがわかる。 Literacy 2 Mathematica

暗号文解読の例

例 (ｄ,n) = (43, 85), C=83

In[1]:=Mod[83^43, 85]

Out[1]=77

したがって、暗号化されたメッセージMは７

(16)

31

クラックの仕方

①

Bobの公開鍵(e,n)を手に入れる。

②

ｎを因数分解して、p,qを推測する。

③

ｐ,qとeを使ってｄを推測する。

④

Aliceが作った暗号文を(d,n)を使って

解読する。

クラックの例

① (e,n)=(3,85) ：公開鍵 C=83：暗号文とする。

②

_{nの因数分解}

In[4]:=Divisors[85] Out[4]={1,5,17,85} ８５は５と１７に因数分解できる。

③

_{ExtendedGCDを使ってdを推定する}

In[9]:=｛g, {d, k}} = ExtendedGCD[3, (5 - 1)(17 - 1)] Out[9]={1,{-21,1}} In[8]:=d + 64 Out[8]=43

④

_{ｄを使って、Cを解読する。}

In[1]:=Mod[83^43, 85] Out[1]=77 ᙔ↓䚮⛆ᐠ㘵d䛵▩䜏䛰䛊

(17)

33

Exercise 1.

Check Euler’s Theorem by Mathematica.

①

Make a list of the function

f(m)=Mod[a^(m),n] from m=１ to the

Euler number of n, where a is an

arbitrary number, n is a prime number.

②

_{Check when does f(m)=1 hold for}

different values of a and n?

Exercise 2. Encrypt your message

①

Set a particular phrase as your message.

②

Convert your message into a sequence of

integers M.

③

Choose a pair of 2-digit prime numbers (p,q)

and derive the keys (d,e,n).

(18)

35

Exercise 3. Crack my

message

Crack me!

Public key: (e,n) = (937, 46127)

 Encrypted message: {14942, 16840, 39519, 6259, 6259, 12812, 33935, 2736, 6259, 30900, 39211, 32709, 4943, 39211, 34710, 4943, 45747, 6259, 19266, 19461, 25615, 27469, 6259, 6259, 14942, 1494, 39519, 6259, 7357, 12408, 39211, 6259, 40186, 2736, 10334, 6259, 45747, 4943, 44980, 15131, 40186, 19991, 34710, 6259, 34710, 33935, 30900, 37515, 6259, 42569, 4943, 37515, 37515, 12408, 41505, 4943, 6259, 22680, 30900, 34710, 33935, 2736, 10334, 34710, 6259, 10334, 37515, 30900, 39211, 41505, 6259, 34710, 33935, 4943, 6259, 24879, 4943, 40186, 37515, 27469}  Guess my original message and my secret key.