|
|||||||||
PREV CLASS NEXT CLASS | FRAMES NO FRAMES | ||||||||
SUMMARY: INNER | FIELD | CONSTR | METHOD | DETAIL: FIELD | CONSTR | METHOD |
java.lang.Object | +--cryptix.provider.rsa.RSAAlgorithm
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:
Copyright © 1997
Systemics Ltd on behalf of the
Cryptix Development Team.
All rights reserved.
$Revision: 1.7 $
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 |
|
Method Detail |
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)
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) andand then combining the two by the CRT.
q2 = plain**d (mod q)
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)) andthen combining these two speedups, we only need to evaluate:
eq = d (mod phi(q))
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) andwe can say that:
Y = q2 (mod q)
Y = q2 + kqand 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.
public static java.math.BigInteger rsa(java.math.BigInteger X, java.math.BigInteger n, java.math.BigInteger exp)
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).
|
|||||||||
PREV CLASS NEXT CLASS | FRAMES NO FRAMES | ||||||||
SUMMARY: INNER | FIELD | CONSTR | METHOD | DETAIL: FIELD | CONSTR | METHOD |