RSA Cryptosystem

Every encryption will have K, so
RSA K ={ (n p q a e): ae congruent to 1 mod phi(n) },
just remember front and back are public key for encryption purpose,
the rest are private key.

so n , e are public key

encryption: e(x) = x^{e} mod n-->n , e are public key


decryption: d(y) = y^{a} mod n


where a is multiplicative invers of
e mod phi(n) --> e^{-1} mod phi (n)
since n = pq, ( p is prime, q is prime),
so phi(n) = phi(q) x phi(p)


q always bigger than p, q - p = 2d > 0
extra 2 formula : -
1) (q - p)/2 = d
2) (p + q)/2 = sqrt( n + d^{2}) ******* to be used for below step 2
[(p + q)/2]^{2} = n + d^{2}


a) How to factoring?
....as long as we can find the d to be sqrt to an integer
let n = 18923
step 1: take sqrt(18923) = 137.56
= Math.Ceiling rounds up (137.56 ) = 138

step 2: 138^{2} = 19044, 18923 + 121 = 19044
18923 + 121 = 138^{2}
formula above (2), n + d^{2}= [(p + q)/2]^{2}
........so sqrt(121) = 11 = d

step 3: now we can have 2 equation to solve the p and q
(1)........q - p = 2d , q - p = 2(11), q - p = 22
(2)........p +q = (2)138
(1) + (2) .........2q = (2)138 + 22,2q = 298,q=149
substiute q = 149 into (2).......p = (2)138 - 149 = 127


solved, n = pq, 18923 = 127 x 149


b) encryption
e(x) = x^{e} mod n, let e = 1261
encrypt x = 2, e(2) = 2^{1261} mod 18923
caculation:-
2^{10} = 1024 mod 18923 ..............all mod 18923
.......always take the previous to be square,
e.g. (2^{10} )^{2} = (1024 )^{2} mod 18923 ,2^{20} = ?
2^{20} = 1024^{2} mod 18923
= 1048576 mod 18923
= 7811

///////////// technique using calculator start /////////////////////
(....technique using calculator, **becareful,
step 1: 1024 --> 'x2' -> 'a b/c' -> 18923
....screen will appear 1024^2 ] 18923
step 2: '='....screen will appear 55.4127781
..........so we can see the number before decimal is 55, so
we minus 55
step3 : 'Ans' - 55....screen will appear 0.4127781
..........since we mod with 18923 ,
so times with 18923
step4 : 'Ans' ->'x' ->18923
....screen will appear 7811
.....p/s: if we see ans 7811.9999 then ans will be 7812,
if ans is 7811.00000888 then ans will be 7811
)end of technique
if hard to understand just use traditional way to deal with it
//////////// technique using calculator end ///////////////////

2^{40} = 7811^{2} mod 18923 = 3969
2^{80} = 3969^{2} mod 18923 = 9025
2^{160} = 9025^{2} mod 18923 = 6033
2^{320} = 6033^{2} mod 18923 = 8160
2^{640} = 8160^{2} mod 18923 = 14486


start to calculate 2^{1261} mod 18923
(^^ just like last time SPM we do decimal changed to binary)
step 1:..noted 1261 enough to be minus by 640 so we put 1 and take remainder
step 2:..noted 621 enough to be minus by 320 so we put 1 and take remainder
step 3:..noted 301 enough to be minus by 160 so we put 1 and take remainder
step 4:..noted 141 enough to be minus by 80 so we put 1 and take remainder
step 5:..noted 61 enough to be minus by 40 so we put 1 and take remainder
step 6:..noted 21 enough to be minus by 20 so we put 1 and take remainder
step 7:..noted 1 will be 2^{1}


................2^ {1} g
2^{10} = 1024
2^{20} = 7811 ..............1 ( 21- 20= 1) f
2^{40} = 3969 ..............1 ( 61- 40 = 21) e
2^{80} = 9025 ..............1 ( 141 - 80 = 61) d
2^{160} = 6033 ..............1 ( 301 - 160 = 141 ) c
2^{320} = 8160 ..............1 ( 621- 320= 301) b
2^{640} = 14486 ..............1 ( 1261 - 640 = 621) a


calculate from bottom to up:-
ans = a x b x c x d x e x f x g mod 18923
a x b mod 18923 = 14486 x 8160 mod 18923 =12702
a x b x c mod 18923 = 12702 x 6033 mod 18923 =11939
a x b x c x d mod 18923 = 11939 x 9025 mod 18923 =1913
a x b x c x d x e mod 18923 = 1913 x 3969 mod 18923 =4574
a x b x c x d x e x f mod 18923 = 4574 x 7811 mod 18923 = 890
a x b x c x d x e x f x g mod 18923 = 890 x 2 mod 18923 = 1780


......so ans, encrypt x = 2, e(2) = 2^{1261} mod 18923
encrypted of 2 is 1780


c)decryption
find the e^{-1} mod phi(n)
d(y) = y^{a} mod n


........becareful here RSA decryption is mod phi(n) NOT mod n
example:
n = 18923 , e = 1261, .........as we calculated in the beginning
so , we have ,n = pq, 18923 = 127 x 149
phi(n) = phi(p) x phi(q) ........please refer my Euler Function
phi(18923 ) = phi(127 ) x phi(149 )
= 126 x 148
= 18648............phi(n)


now, in order to decrypt we need to find multiplicative inverse of
exponent (e^{-1}) in which is 'a' in the formula..............pls
refer to my "Multiplicative Inverse"
find, e^{-1} mod phi(n) = 1261^{-1} mod 18648
= 5797..............a
d(y) = y^{a} mod n , if my friend send me 1780, so i have to
decrypt it.
d(1780) = 1780^{5797} mod 18923


start prepare calculation:-
1780^{1} ..............1
1780^{2} = 8259 mod 18923
1780^{4} = 12589 mod 18923 ..............1
1780^{8} = 2796 mod 18923
1780^{16} = 2417 mod 18923
1780^{32} = 13605 mod 18923 ..............1
1780^{64} = 10162 mod 18923
1780^{128} = 3433 mod 18923 ..............1
1780^{256} = 15383 mod 18923
1780^{512} = 4574 mod 18923 ..............1
1780^{1024} = 11561 mod 18923 ..............1
1780^{2048} = 3572 mod 18923
1780^{4096} = 5082 mod 18923 ..............1 ( 5797- 4096=1701)


5082 x 11561 =16010 x4574 =16653 x 3433 =3366 x13605 =770 x12589
=4954 x1780 = 2 mod 18923


...........congratulation, you are master ^^ haha, dont beat me.
ans is 2 ( plaintext)