Docjar: A Java Source and Docuemnt Enginecom.*    java.*    javax.*    org.*    all    new    plug-in

Quick Search    Search Deep

cryptix.jce.provider.pk
Class RSAAlgorithm  view RSAAlgorithm download RSAAlgorithm.java

java.lang.Object
  extended bycryptix.jce.provider.pk.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:

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.6 $

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.