rsa Class Reference

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

Public Member Functions
long	generateKeys (long p, long q)
	Generates the public and private keys. More...
long	encrypt (long val)
	Encrypts a number. More...
long	decrypt (long val)
	Decrypts a number. More...

Static Public Member Functions
static void	main (String[] args)
	Main function for testing. More...

Private Member Functions
long	fixRemainder (long a, long b)
	Calculates the correct remainder if (a % b) has the opposite sign of b. More...
long	egcd (long a, long b, long[]last)
	The extended Euclidean algorithm for the Greatest Common Divisor of two integers. More...
long	modinv (long a, long m)
	Calculates the modular inverse of a long. More...
long	modinv2 (long a, long b, long c)
	Calculates the modular inverse of a long. More...
long	power_mod_n (long c, long d, long n)
	Calculates c to the power of d mod n. More...

Static Private Attributes
static long	n
	p*q. More...
static long	d
	Private key: (n,d). More...
static long	e
	Public key: (n,e). More...

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 word. 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, φ = (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, -n+2 < m < n.
6. m = \(c^{d}\) mod n.

To compile:

• javac rsa.java

To execute:

• java rsa

Author

Paulo Roma

Since

08/03/2013

See also

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

http://www2.webster.edu/~lovedo/COSC_1570/RSA.htm

Definition at line 37 of file rsa.java.

Member Function Documentation

decrypt()

long rsa.decrypt

(

long

val

)

Decrypts a number.

Parameters

val	given number.

Returns

decrypted number.

Definition at line 204 of file rsa.java.

References d, n, and power_mod_n().

Referenced by main().

egcd()

long rsa.egcd ( long  a, long  b, long[]  last  )

private

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

Parameters

a	first integer.
b	second integer.
last	x and y as below.

Returns

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

Definition at line 80 of file rsa.java.

Referenced by main(), and modinv().

encrypt()

long rsa.encrypt

(

long

val

)

Encrypts a number.

Parameters

val	given number.

Returns

encrypted number.

Definition at line 196 of file rsa.java.

References e, n, and power_mod_n().

Referenced by main().

fixRemainder()

long rsa.fixRemainder ( long  a, long  b  )

private

Calculates the correct remainder if (a % b) has the opposite sign of b.

In C, 17 % -4 = 1, 18 % -4 = 2, 19 % -4 = 3, 20 % -4 = 0 but it shoud be -3, -2, -1 and 0:

e.g., \(\frac{17}{-4}=-4,\) plus a remainder \(\Rightarrow 17 = -4 \times -4+1\), but \(17 =-5 \times -4-3\), either.

Parameters

a	dividend.
b	divisor.

Returns

correct remainder.

Definition at line 62 of file rsa.java.

Referenced by modinv().

generateKeys()

long rsa.generateKeys	(	long	p,
		long	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

0 if no error has occurred, and phi otherwise.

Definition at line 181 of file rsa.java.

References d, e, modinv(), and n.

Referenced by main().

main()

static void rsa.main ( String[]  args )

static

Main function for testing.

Parameters

args	number1, number2, prime size.

Definition at line 213 of file rsa.java.

References d, decrypt(), e, egcd(), encrypt(), generateKeys(), modinv(), and n.

modinv()

long rsa.modinv ( long  a, long  m  )

private

Calculates the modular inverse of a long.

d * a = 1 mod m

Parameters

a	given long.
m	divisor.

Returns

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

Definition at line 110 of file rsa.java.

References egcd(), and fixRemainder().

Referenced by generateKeys(), and main().

modinv2()

long rsa.modinv2 ( long  a, long  b, long  c  )

private

Calculates the modular inverse of a long.

d * a = c mod b

Parameters

a	given long.
b	divisor.
c	generally 1.

Returns

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

Definition at line 130 of file rsa.java.

power_mod_n()

long rsa.power_mod_n ( long  c, long  d, long  n  )

private

Calculates c to the power of d mod n.

Parameters

c	base.
d	exponent.
n	divisor.

Returns

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

Definition at line 148 of file rsa.java.

References d, e, n, and baseConverter.reverseBits().

Referenced by decrypt(), and encrypt().

Member Data Documentation

d

long rsa.d

staticprivate

Private key: (n,d).

Definition at line 45 of file rsa.java.

Referenced by decrypt(), generateKeys(), main(), and power_mod_n().

e

long rsa.e

staticprivate

Public key: (n,e).

Definition at line 49 of file rsa.java.

Referenced by encrypt(), generateKeys(), main(), and power_mod_n().

n

long rsa.n

staticprivate

p*q.

Definition at line 41 of file rsa.java.

Referenced by decrypt(), encrypt(), generateKeys(), main(), and power_mod_n().

---

The documentation for this class was generated from the following file:

• rsa.java