All Packages  Class Hierarchy  This Package  Previous  Next  Index

Class cryptix.provider.rsa.RSAAlgorithm

java.lang.Object
   |
   +----cryptix.provider.rsa.RSAAlgorithm

public final class RSAAlgorithm
extends 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 $

Author:
Raif S. Naffah, David Hopwood

Method Index

 o rsa(BigInteger, BigInteger, BigInteger)
Computes the RSA algorithm, without using the Chinese Remainder Theorem.
 o rsa(BigInteger, BigInteger, BigInteger, BigInteger, BigInteger, BigInteger)
Computes the RSA algorithm.

Methods

 o rsa
 public static BigInteger rsa(BigInteger X,
                              BigInteger n,
                              BigInteger exp,
                              BigInteger p,
                              BigInteger q,
                              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.
 o rsa
 public static BigInteger rsa(BigInteger X,
                              BigInteger n,
                              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.

All Packages  Class Hierarchy  This Package  Previous  Next  Index