Mathematica 3 Hiroshi Toyoizumi Univ. of Aizu toyo@u-aizu.ac.jp REFERENCES [1] C.P Williams [2] [3] 1 Mathematica Mathematica 2 1
PKIPublic Key Infrustructure 3 4 2
5 6 3
RSA 3Ronald RivestAdi ShamirLeonald AdlemanRSA 20009 DSA Diffie-Hellman Whitfield DiffieMartin E. Hellman Diffie1976 Hellman New Directions in CryptographyRSA3 RSA 7 Mathematica Mod GCD FactorInteger Divisors Prime PrimeQ ExtendGCD EulerPhi 8 4
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. 9 Mod Mod[m, n] gives the remainder on division of m by n. 10 5
GCD GCD gives the greatest common divisor of the integers 11 FactorInteger[n] FactorInteger [n] gives a list of the prime factors of the integer n, together with their exponents. 12 6
Divisors[n] Divisors[n] gives a list of the integers that divide n. 13 Prime Prime[n] gives the n- th prime number. 14 7
PrimeQ[expr] PrimeQ[ex pr] yields True if expr is a prime number, and yields False otherwise.n 15 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 16 8
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 17 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] Out[1]= 4 In[2]:= Select[Range[10],GCD[#1,10]==1&] Out[2]= {1,3,7,9} 18 9
Euler a GCD(a,n)=1 aφ(n) = 1 mod n 19 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 20 10
RSA 21 22 11
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 23 : e d = 1 mod (p-1)(q-1) d d=43 e d = 3*43 = 129 = 64 *2 +1 = 1 mod 64 24 12
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)α 25 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 26 13
Bob(e,n) AliceBob 27 Alice M Bobe,n)C C = M^e mod n (e,n) = (3, 85), M=77 In[1]:=Mod[77^3, 85] Out[1]=83 C 28 14
Bob AliceC 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 MpqEuler = M mod pq MM=jp = j {j^k(p-1)}^q mod q Euler = j mod q = M mod pq M C^d=M mod n 29 (,n) = (43, 85), C=83 In[1]:=Mod[83^43, 85] Out[1]=77 M 30 15
Bob(e,n) p,q,qe Alice(d,n) 31 (e,n)=(3,85) C=83 n In[4]:=Divisors[85] Out[4]={1,5,17,85} ExtendedGCDd 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 32 16
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? 33 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). Encrypt M into C by the key (e,n). Check if C can be decrypted by the key (d,n). Option: Ask your neighbors to decrypt C by disclosing your public key (e,n). 34 17
Exercise 3.Crack my message Crack me! Public key: (e,n) = (937, 46127) Encryptedmessage:{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. Option: Answer my questions in the original message. 35 Exercise 4 (Option). Performance Evaluation of Cracking Use Timing[ ] function and estimate the CPU time required to crack RSA with given n. Draw the graph (log-log plot?) of CPU time with different n. Discuss the possibility of cracking when n is large. 36 18
Timing Timing[expr] evaluates expr, and returns a list of time used, together with the result obtained. Timing gives the CPU time in seconds, multiplied by the symbol Second. Example:Here is the CPU time needed to compute a large factorial number. In[11]:=Timing[10^10!] Out[11]={5.8 Second,Null} 37 19