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:

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