RSA: Faster Decryption using CRT

This article is to discuss about “RSA: Faster Decryption using CRT”

def crt(n, a):
    sum = 0
    prod = reduce(lambda a, b: a*b, n)
 
    for n_i, a_i in zip(n, a):
        p = prod / n_i
        sum += a_i * mulInv(p, n_i) * p
    return sum % prod
 
 
def mulInv(a, b):
    b0 = b
    x0, x1 = 0, 1
    if b == 1: return 1
    while a > 1:
        q = a / b
        a, b = b, a%b
        x0, x1 = x1 - q * x0, x0
    if x1  1:
        raise Exception('unexpected')
    if t < 0:
        t += n
    return t

if __name__ == '__main__':
	# Faster decryption using CRT
	# We have this
	p, q = 223, 149
	e = 29
	C = 29869
	# ? Find: M
	
	# Prequisite: We don't know this	
	M = 82
	N = p*q
	print M < N
	
	# Let's Play
	dp = invMod(e, p-1)
	dq = invMod(e, q-1)
	
	Mp = C**dp
	Mq = C**dq
	
	n = [p, q]
	a = [Mp, Mq]
	M2 = crt(n, a)
	assert M == M2

Hope it is useful…

Talk Less Code More

Advertisements

Leave a Reply

Fill in your details below or click an icon to log in:

WordPress.com Logo

You are commenting using your WordPress.com account. Log Out / Change )

Twitter picture

You are commenting using your Twitter account. Log Out / Change )

Facebook photo

You are commenting using your Facebook account. Log Out / Change )

Google+ photo

You are commenting using your Google+ account. Log Out / Change )

Connecting to %s