Overview  Package   Class  Use  Deprecated  Index
Home >> All >> cryptix >> jce >> provider >> [ rsa overview ]	PREV CLASS  NEXT CLASS
SUMMARY:  JAVADOC |  SOURCE |  DOWNLOAD | NESTED | FIELD | CONSTR | METHOD	DETAIL: FIELD | CONSTR | METHOD

---

cryptix.jce.provider.rsa
Class RSAAlgorithm  

java.lang.Object
  cryptix.jce.provider.rsa.RSAAlgorithm

---

final class RSAAlgorithm

extends java.lang.Object

A class that calculates the RSA algorithm. A single method is used for encryption, decryption, signing and verification:

• for encryption and verification, the public exponent, e, should be given.
• for decryption and signing, the private exponent, d, should be given.

The purpose of having this as a separate class is to avoid duplication between the RSA Cipher and Signature implementations.

References:

1. Donald E. Knuth, The Art of Computer Programming, ISBN 0-201-03822-6 (v.2) pages 270-274.

2. ANS X9.31, Appendix B.

Version:

$Revision: 1.5 $

---

Field Summary
private static java.math.BigInteger	ONE           Not present in JDK 1.1

 

Constructor Summary
private	RSAAlgorithm()           static methods only

 

Method Summary
static java.math.BigInteger	rsa(java.math.BigInteger X, java.math.BigInteger n, java.math.BigInteger exp)           Computes the RSA algorithm, without using the Chinese Remainder Theorem.
static java.math.BigInteger	rsa(java.math.BigInteger X, java.math.BigInteger n, java.math.BigInteger exp, java.math.BigInteger p, java.math.BigInteger q, java.math.BigInteger u)           Computes the RSA algorithm.
static java.math.BigInteger	rsa(java.math.BigInteger X, java.math.BigInteger modulus, java.math.BigInteger exp, java.math.BigInteger primeP, java.math.BigInteger primeQ, java.math.BigInteger primeExponentP, java.math.BigInteger primeExponentQ, java.math.BigInteger crtCoefficient)

 

Methods inherited from class java.lang.Object

clone, equals, finalize, getClass, hashCode, notify, notifyAll, toString, wait, wait, wait

 

Field Detail

ONE

private static final java.math.BigInteger ONE

Not present in JDK 1.1

Constructor Detail

RSAAlgorithm

private RSAAlgorithm()

static methods only

Method Detail

rsa

public static java.math.BigInteger rsa(java.math.BigInteger X,
                                       java.math.BigInteger n,
                                       java.math.BigInteger exp,
                                       java.math.BigInteger p,
                                       java.math.BigInteger q,
                                       java.math.BigInteger u)

Computes the RSA algorithm. If p is null, straightforward modular exponentiation is used.

Otherwise, this method uses the Chinese Remainder Theorem (CRT) to compute the result given the known factorisation of the public modulus n into two relatively prime factors p and q. The arithmetic behind this method is detailed in [1] and [2].

The comments that follow, which are edited from the PGP mpilib.c file with p and q reversed, make the practical algorithmic implementation clearer:

Y = X**d (mod n) = X**d (mod pq)

We form this by evaluating:

p2 = plain**d (mod p) and
q2 = plain**d (mod q)

and then combining the two by the CRT.

Two optimisations of this are possible. First, we reduce X modulo p and q before starting, since:

x**a (mod b) = (x (mod b))**a (mod b)

Second, since we know the factorisation of p and q (trivially derived from the factorisation of n = pq), and input is relatively prime to both p and q, we can use Euler's theorem:

X**phi(m) = 1 (mod m),

to throw away multiples of phi(p) or phi(q) in d. Letting

ep = d (mod phi(p)) and
eq = d (mod phi(q))

then combining these two speedups, we only need to evaluate:

p2 = (X mod p)**ep (mod p) and
q2 = (X mod q)**eq (mod q).

Now we need to apply the CRT. Starting with:

Y = p2 (mod p) and
Y = q2 (mod q)

we can say that:

Y = q2 + kq

and if we assume that:

0 <= q2 < q, then
0 <= Y < pq for some 0 <= k < p

Since we want:

Y = p2 (mod p),

then

kq = (p2 - q2) (mod q)

Since p and q are relatively prime, q has a multiplicative inverse u mod p. In other words, uq = 1 (mod p).

Multiplying by u on both sides gives:

k = u * (p2 - q2) (mod p)

Once we have k, evaluating kq + q2 is trivial, and that gives us the result.

---

rsa

public static java.math.BigInteger rsa(java.math.BigInteger X,
                                       java.math.BigInteger modulus,
                                       java.math.BigInteger exp,
                                       java.math.BigInteger primeP,
                                       java.math.BigInteger primeQ,
                                       java.math.BigInteger primeExponentP,
                                       java.math.BigInteger primeExponentQ,
                                       java.math.BigInteger crtCoefficient)

---

rsa

public static java.math.BigInteger rsa(java.math.BigInteger X,
                                       java.math.BigInteger n,
                                       java.math.BigInteger exp)

Computes the RSA algorithm, without using the Chinese Remainder Theorem.

---

Overview  Package   Class  Use  Deprecated  Index
Home >> All >> cryptix >> jce >> provider >> [ rsa overview ]	PREV CLASS  NEXT CLASS
SUMMARY:  JAVADOC |  SOURCE |  DOWNLOAD | NESTED | FIELD | CONSTR | METHOD	DETAIL: FIELD | CONSTR | METHOD

---