Situatie
RSA decryption is slower than encryption because while doing decryption, private key parameter ” d ” is necessarily large. Moreover the parameters – ” p and q ” are two very large Prime Numbers. Given integers c, e, p and q, find m such that c = pow(m, e) mod (p * q) (RSA decryption for weak integers).
Solutie
Pasi de urmat
- RSA is a public key encryption system used for secure transmission of messages.
- RSA involves four steps typically : (1) Key generation (2) Key distribution (3) Encryption (4) Decryption
- Message Encryption is done with a “Public Key”.
- Message Decryption is done with a “Private Key” – parameters (p, q, d) generated along with Public Key.
- The private key is known only to the user, and the public key can be made known to anyone who wishes to send an encrypted message to the person with the corresponding private key.
- A public key which is depicted by two parameters n (modulus) and e (exponent). The modulus is a product of two very large prime numbers (p and q as shown below). Decryption of this message would require the user to factorize n into two prime factors(the main reason, RSA is secure), and then find the modular inverse of e, wherein the difficult task lies.
- A text message is first converted to the respective decimal value, which is the parameter ‘m’ which we are finding below. We now encrypt this message by doing c = pow(m, e) mod (p * q), where c is the encrypted text.
# Function to find the gcd of two
# integers using Euclidean algorithm
def gcd(p, q):
if q == 0:
return p
return gcd(q, p % q)
# Function to find the
# lcm of two integers
def lcm(p, q):
return p * q / gcd(p, q)
# Function implementing extended
# euclidean algorithm
def egcd(e, phi):
if e == 0:
return (phi, 0, 1)
else:
g, y, x = egcd(phi % e, e)
return (g, x – (phi // e) * y, y)
# Function to compute the modular inverse
def modinv(e, phi):
g, x, y = egcd(e, phi)
return x % phi
# Implementation of the Chinese Remainder Theorem
def chineseremaindertheorem(dq, dp, p, q, c):
# Message part 1
m1 = pow(c, dp, p)
# Message part 2
m2 = pow(c, dq, q)
qinv = modinv(q, p)
h = (qinv * (m1 – m2)) % p
m = m2 + h * q
return m
# Driver Code
p = 9817
q = 9907
e = 65537
c = 36076319
d = modinv(e, lcm(p – 1, q – 1))
“””
pow(a, b, c) calculates a raised to power b
modulus c, at a much faster rate than pow(a, b) % c
Furthermore, we use Chinese Remainder Theorem as it
splits the equation such that we have to calculate two
values whose equations have smaller moduli and exponent
value, thereby reducing computing time.
“””
dq = pow(d, 1, q – 1)
dp = pow(d, 1, p – 1)
print chineseremaindertheorem(dq, dp, p, q, c)
Leave A Comment?