The setup for RSA

Math 202 Cryptography, October 12, 2016
T. Ratliff, Wheaton College
ratliff_thomas@wheatoncollege.edu

Finding d if (Subscript[k, pub])=(25021,3)

We need to factor n=25021

FactorInteger[25021]

Thus, n=131 x 191 and ϕ(n)=130(190) = 24700
We can find d using the Extended Euclidean Algorithm

ExtendedGCD[3, 24700]

Thus, -8233(3) + 1(24700) = 1 and (3^(-1))≡ -8233 mod 24700 or

Mod[-8233,24700]

Thus d=16467.  Let verify.

Mod[3*16467, 24700]

Generating actual values for RSA

A 1024-bit prime will lie between (2^1023) and (2^1024)-1

p=RandomPrime[{2^1023,2^1024 -1}]
q=RandomPrime[{2^1023,2^1024-1}]
n=p*q

Let’s check if 3 and ϕ(n)=(p-1)(q-1) are relatively prime. 
If not, will need to check another value to use for e.
Then we can find d

ExtendedGCD[3,(p-1)*(q-1)]