Simple implementation of RSA algorithm, asymmetric cryptography algorithm
The concept of RSA Algorithm is generating public and private keys in 512 bits.
• Choose two random prime numbers p & q using Miller-Rabin Test
• Compute n =p*q
• Compute euler phi = (p-1) (q-1)
• Choose e, random prime number in specific range
• Then get the key of (n,e)
• C = m^e mod n
• C^d mod n
• e^-1 mod phi
1- Get U & R from the prime number
2- Use Square and multiply algorithm to allow fast exponentiaition
1- Modular representation of y into p and q
𝑦𝑝=𝑦 𝑚𝑜𝑑 𝑝
𝑦𝑞=𝑦 𝑚𝑜𝑑 𝑞
2- Compute exponents
𝑑𝑝=𝑑 𝑚𝑜𝑑 (𝑝−1)
𝑑𝑞=𝑑 𝑚𝑜𝑑 (𝑞−1)
3- Compute exponentiation
𝑥𝑝=𝑦𝑝𝑑𝑝 𝑚𝑜𝑑 𝑝
𝑥𝑞=𝑦𝑞𝑑𝑞 𝑚𝑜𝑑 𝑞
4- Compute C:
𝐶𝑝=𝑞−1 𝑚𝑜𝑑 𝑝
𝐶𝑞=𝑝−1 𝑚𝑜𝑑 𝑞
5- Compute X
𝑋 = {(𝑞.𝐶𝑝)𝑋𝑝 + (𝑝.𝐶𝑞) 𝑋𝑞} 𝑚𝑜𝑑 𝑛