_05d_rsa Namespace Reference

An RSA algorithm for public-key cryptography. More...

Functions
def	egcd (a, b)
	The extended Euclidean algorithm for the Greatest Common Divisor of two integers. More...
def	modinv (a, m)
	Calculates the modular inverse of an integer. More...
def	modinv2 (a, b, c)
	Calculates the modular inverse of an integer. More...
def	power_mod_n (c, d, n)
	Calculates c to the power of d mod n. More...
def	generateKeys (p, q)
	Generates the public and private keys. More...
def	main ()

Detailed Description

An RSA algorithm for public-key cryptography.

The RSA algorithm is named after Ron Rivest, Adi Shamir and Len Adleman, who invented it in 1977. The basic technique was first discovered in 1973 by Clifford Cocks of CESG (part of the British GCHQ), but this was a secret until 1997. The patent taken out by RSA Labs has expired.

The RSA cryptosystem is the most widely-used public key cryptography algorithm in the world. It can be used to encrypt a message without the need to exchange a secret key separately.

The RSA algorithm can be used for both public key encryption and digital signatures. Its security is based on the difficulty of factoring large integers.

Summary of RSA

1. n = pq, where p and q are distinct primes.
2. phi, \( \varphi = (p-1)(q-1)\)
3. e < n such that gcd(e, phi)=1
4. d = \(e^{-1}\) mod phi.
5. c = \(m^{e}\) mod n, 1 < m < n.
6. m = \(c^{d}\) mod n.

Author

Paulo Roma

Since

19/02/2012

See also

http://www.di-mgt.com.au/rsa_alg.html

Function Documentation

egcd()

def _05d_rsa.egcd	(		a,
			b
	)

The extended Euclidean algorithm for the Greatest Common Divisor of two integers.

Parameters

a	first integer
b	second integer.

Returns

The tuple (x, y, gcd(a, b)) where x and y satisfy the equation ax + by = gcd(a, b)

Referenced by main(), and modinv().

generateKeys()

def _05d_rsa.generateKeys	(		p,
			q
	)

Generates the public and private keys.

In practice, common choices for e are 3, 17 and 65537 \((2^{16}+1)\). These are Fermat primes, sometimes referred to as \(F_0, F_2\) and \(F_4\) respectively \((F_x=2^{2^x}+1)\). They are chosen because they make the modular exponentiation operation faster.

Also, having chosen e, it is simpler to test whether gcd(e, p-1)=1 and gcd(e, q-1)=1 while generating and testing the primes p and q. Values of p or q that fail this test can be rejected there and then.

(Even better: if e is prime and greater than 2 then you can do the less-expensive test: (p mod e)!=1 instead of gcd(p-1,e)==1.)

Parameters

p	a big prime number.
q	another prime number.

Returns

(n, d, e, phi) or p*q, private key (n,d), public key (n,e), (p-1)*(q-1).

References modinv().

Referenced by main().

main()

def _05d_rsa.main

(

)

References egcd(), generateKeys(), _01d_dec2bin.input, modinv(), and power_mod_n().

modinv()

def _05d_rsa.modinv	(		a,
			m
	)

Calculates the modular inverse of an integer.

d * a = 1 mod m

Parameters

a	given integer.
m	divisor.

Returns

modular inverse d, or 0 if the modular inverse does not exist.

References egcd().

Referenced by generateKeys(), and main().

modinv2()

def _05d_rsa.modinv2	(		a,
			b,
			c
	)

Calculates the modular inverse of an integer.

d * a = c mod b

Parameters

a	given integer.
b	divisor.
c	generally 1.

Returns

modular inverse d, or 0 if the modular inverse does not exist.

power_mod_n()

def _05d_rsa.power_mod_n	(		c,
			d,
			n
	)

Calculates c to the power of d mod n.

Parameters

c	base.
d	exponent.
n	divisor.

Returns

\(c^d\ \%\ n\)

Referenced by main().