Given KU =
encryption: c = m^2 mod n, m < n
decryption: m = c^d mod n
signature: s = m^d mod n, m < n
verification: m = s^e mod n
Given pub =
n = p*q,Θ(n) = (p-1)(q-1)
exd = 1 mod Θ(n)
x^exd = x mod n
encryption: c = m^e mod n
decryption: m = c^d mod n = m^exd mod n = m mod n = m(since m < n)
digital signature (similar)
88^7 mod 187 = 11 -> 11^23 mod 187 = 88 -> plaintext 88
Factoring an integer with at least 512-bit is very hard!
But if you can factor big number n then given public key
knowing factors p, q, such that, n = p*q
then compute Θ(n)=(p-1)(q-1)
then find d such tat exd = 1 mod Θ(n)
