cryptix.provider.rsa

Class RSAAlgorithm

java.lang.Object

cryptix.provider.rsa.RSAAlgorithm

public 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.

Copyright © 1997 Systemics Ltd on behalf of the Cryptix Development Team.
All rights reserved.

$Revision: 1.7 $

Since:

Cryptix 2.2.2

Author:

Raif S. Naffah, David Hopwood

Method Summary

Modifier and Type	Method and Description
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.

Methods inherited from class java.lang.Object

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

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.

Parameters:

X - the BigInteger to be used as input.

n - the public modulus.

exp - the exponent (e for encryption and verification, d for decryption and signing).

p - the first factor of the public modulus.

q - the second factor of the public modulus.

u - the multiplicative inverse of q modulo p.

Returns:

the result of the computation.

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.

Parameters:

X - the BigInteger to be used as input.

n - the public modulus.

exp - the exponent (e for encryption and verification, d for decryption and signing).

Returns:

the result of the computation.