︠0fa7e962-8d7f-42a9-be29-613e3dd66e83s︠
#This small worksheet allows you to test your RSA p and q and find for a given e the d such that e d = 1 mod phi(p*q)
#
# Set p and q
#
p= 127;
q= 43;
is_prime(q) and is_prime(p)
︡aa071265-808e-4d51-b104-69b3b22d9aa5︡︡{"stdout":"True\n","done":false}︡{"done":true}
︠8ff656ff-2d3c-4809-954b-95c6c7d63493s︠
factor(p-1);
︡13950bd0-13e3-48b9-9c8b-68da39473dd4︡︡{"stdout":"2 * 3^2 * 7\n","done":false}︡{"done":true}
︠21628f1e-60c0-425b-942d-b46dd303fa4ds︠
factor(q-1);
︡ae28c707-4094-4020-940f-24d2799882ef︡︡{"stdout":"2 * 3 * 7\n","done":false}︡{"done":true}
︠8e833e59-8349-4b61-99ee-cae31334391ds︠
# Set e, and factor it
#
e = 5
factor(e);
︡f11be510-a489-450c-a8b0-db68f2843eb2︡︡{"stdout":"5\n","done":false}︡{"done":true}
︠c6f819cb-a428-4e03-8a42-0e759fd34b5c︠
︠dc43debd-3e97-4471-be4a-dd51effe6bb4s︠
phi= (p-1)*(q-1); phi;
︡a1289ae2-1bbd-4be3-a8ba-fde8fe0b7b61︡︡{"stdout":"5292\n","done":false}︡{"done":true}
︠02ee16c8-0802-411d-ba96-c444ed364f03s︠
# Solved Bezout's identity. That is
# Compute (D, s, t) such that D=gcd(a,b) = s*a + t*b
#
bezout = xgcd(e, phi); bezout;
︡adf83c56-939b-46ab-b69c-92506fcca368︡︡{"stdout":"(1, 2117, -2)\n","done":false}︡{"done":true}
︠f4f70166-5289-4b12-9706-7cbfb7b6960es︠
# this will be now our inverse of e mod phi
#
d = bezout[1]; d;
︡f66b8fa4-fa9d-4d58-9a7c-c10b5603a231︡︡{"stdout":"2117\n","done":false}︡{"done":true}
︠6681f941-539e-4399-906d-1b3035d16a98s︠
# check if its true
#
t = mod( (d*e), phi);t;
︡8f658e98-7c39-4ea8-8dca-ae5b55eeb2dc︡︡{"stdout":"1\n","done":false}︡{"done":true}
︠c9b339fc-859d-4450-961d-9d82987149bf︠