cryptix.provider.rsa
public final class RSAAlgorithm extends Object
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 $
Since: Cryptix 2.2.2
Method Summary | |
---|---|
static BigInteger | rsa(BigInteger X, BigInteger n, BigInteger exp, BigInteger p, BigInteger q, BigInteger u)
Computes the RSA algorithm. |
static BigInteger | rsa(BigInteger X, BigInteger n, BigInteger exp)
Computes the RSA algorithm, without using the Chinese Remainder
Theorem.
|
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.
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.