Source code: cryptix/jce/provider/pk/RSAAlgorithm.java
1 /* $Id: RSAAlgorithm.java,v 1.6 2001/10/10 02:55:36 gelderen Exp $
2 *
3 * Copyright (C) 1995-1999 The Cryptix Foundation Limited.
4 * All rights reserved.
5 *
6 * Use, modification, copying and distribution of this software is subject
7 * the terms and conditions of the Cryptix General Licence. You should have
8 * received a copy of the Cryptix General Licence along with this library;
9 * if not, you can download a copy from http://www.cryptix.org/ .
10 */
11 package cryptix.jce.provider.pk;
12
13
14 import java.math.BigInteger;
15
16
17 /**
18 * A class that calculates the RSA algorithm. A single method is
19 * used for encryption, decryption, signing and verification:
20 * <ul>
21 * <li> for encryption and verification, the public exponent, <i>e</i>,
22 * should be given.
23 * <li> for decryption and signing, the private exponent, <i>d</i>,
24 * should be given.
25 * </ul>
26 * <p>
27 * The purpose of having this as a separate class is to avoid duplication
28 * between the RSA Cipher and Signature implementations.
29 * <p>
30 * <b>References:</b>
31 * <ol>
32 * <li> Donald E. Knuth,
33 * <cite>The Art of Computer Programming</cite>,
34 * ISBN 0-201-03822-6 (v.2) pages 270-274.
35 * <p>
36 * <li> <cite>ANS X9.31, Appendix B</cite>.
37 * </ol>
38 *
39 * @version $Revision: 1.6 $
40 * @author David Hopwood
41 * @author Jeroen C. van Gelderen (gelderen@cryptix.org)
42 * @author Raif S. Naffah
43 */
44 /*package*/ final class RSAAlgorithm
45 {
46
47 // Constants
48 //...........................................................................
49
50 /** Not present in JDK 1.1 */
51 private static final BigInteger ONE = BigInteger.valueOf(1L);
52
53
54 // Constructor
55 //...........................................................................
56
57 /** static methods only */
58 private RSAAlgorithm() {}
59
60
61 // Own methods
62 //...........................................................................
63
64 /**
65 * Computes the RSA algorithm. If <i>p</i> is null, straightforward
66 * modular exponentiation is used.
67 * <p>
68 * Otherwise, this method uses the Chinese Remainder Theorem (CRT) to
69 * compute the result given the known factorisation of the public
70 * modulus <i>n</i> into two relatively prime factors <i>p</i> and <i>q</i>.
71 * The arithmetic behind this method is detailed in [1] and [2].
72 * <p>
73 * The comments that follow, which are edited from the PGP
74 * <samp>mpilib.c</samp> file <em>with p and q reversed</em>, make
75 * the practical algorithmic implementation clearer:
76 * <p>
77 * <blockquote>
78 * Y = X**d (mod n) = X**d (mod pq)
79 * </blockquote>
80 * <p>
81 * We form this by evaluating:
82 * <blockquote>
83 * p2 = plain**d (mod p) and <br>
84 * q2 = plain**d (mod q)
85 * </blockquote>
86 * and then combining the two by the CRT.
87 * <p>
88 * Two optimisations of this are possible. First, we reduce X modulo p
89 * and q before starting, since:
90 * <blockquote>
91 * x**a (mod b) = (x (mod b))**a (mod b)
92 * </blockquote>
93 * <p>
94 * Second, since we know the factorisation of p and q (trivially derived
95 * from the factorisation of n = pq), and input is relatively prime to
96 * both p and q, we can use Euler's theorem:
97 * <blockquote>
98 * X**phi(m) = 1 (mod m),
99 * </blockquote>
100 * to throw away multiples of phi(p) or phi(q) in d. Letting
101 * <blockquote>
102 * ep = d (mod phi(p)) and <br>
103 * eq = d (mod phi(q))
104 * </blockquote>
105 * then combining these two speedups, we only need to evaluate:
106 * <blockquote>
107 * p2 = (X mod p)**ep (mod p) and <br>
108 * q2 = (X mod q)**eq (mod q).
109 * </blockquote>
110 * <p>
111 * Now we need to apply the CRT. Starting with:
112 * <blockquote>
113 * Y = p2 (mod p) and <br>
114 * Y = q2 (mod q)
115 * </blockquote>
116 * we can say that:
117 * <blockquote>
118 * Y = q2 + kq
119 * </blockquote>
120 * and if we assume that:
121 * <blockquote>
122 * 0 <= q2 < q, then <br>
123 * 0 <= Y < pq for some 0 <= k < p
124 * </blockquote>
125 * <p>
126 * Since we want:
127 * <blockquote>
128 * Y = p2 (mod p),
129 * </blockquote>
130 * then
131 * <blockquote>
132 * kq = (p2 - q2) (mod q)
133 * <blockquote>
134 * <p>
135 * Since p and q are relatively prime, q has a multiplicative inverse
136 * u mod p. In other words, uq = 1 (mod p).
137 * <p>
138 * Multiplying by u on both sides gives:
139 * <blockquote>
140 * k = u * (p2 - q2) (mod p)
141 * </blockquote>
142 * <p>
143 * Once we have k, evaluating kq + q2 is trivial, and that gives
144 * us the result.
145 *
146 * @param X the BigInteger to be used as input.
147 * @param n the public modulus.
148 * @param exp the exponent (e for encryption and verification,
149 * d for decryption and signing).
150 * @param p the first factor of the public modulus.
151 * @param q the second factor of the public modulus.
152 * @param u the multiplicative inverse of q modulo p.
153 * @return the result of the computation.
154 */
155 public static BigInteger rsa(BigInteger X, BigInteger n, BigInteger exp,
156 BigInteger p, BigInteger q, BigInteger u)
157 {
158 if (p == null)
159 return rsa(X, n, exp);
160
161 // construct the two missing ints
162 BigInteger primeExponentP = exp.mod(p.subtract(ONE));
163 BigInteger primeExponentQ = exp.mod(q.subtract(ONE));
164
165 return rsa(X, n, exp, p, q, primeExponentP, primeExponentQ, u);
166 }
167
168
169 public static BigInteger rsa(BigInteger X,
170 BigInteger modulus,
171 BigInteger exp,
172 BigInteger primeP,
173 BigInteger primeQ,
174 BigInteger primeExponentP,
175 BigInteger primeExponentQ,
176 BigInteger crtCoefficient)
177 {
178 // First check if u = (1/q) mod p; if not exchange p and q
179 // before using CRT. This is needed for factors not generated/set
180 // by cryptix.provider.rsa classes; eg. PGP applications.
181 if( !crtCoefficient.equals(primeQ.modInverse(primeP)) )
182 {
183 BigInteger t;
184
185 t = primeQ; primeQ = primeP; primeP = t;
186
187 t = primeExponentQ;
188 primeExponentQ = primeExponentP;
189 primeExponentP = t;
190 }
191
192 // Factors are known and usable by our CRT code.
193 BigInteger p2 = X.mod(primeP).modPow(primeExponentP, primeP);
194 BigInteger q2 = X.mod(primeQ).modPow(primeExponentQ, primeQ);
195
196 if (p2.equals(q2))
197 return q2;
198
199 BigInteger k = (p2.subtract(q2).mod(primeP));
200 BigInteger l = k.multiply(crtCoefficient).mod(primeP);
201 return primeQ.multiply(l).add(q2);
202 }
203
204
205 /**
206 * Computes the RSA algorithm, without using the Chinese Remainder
207 * Theorem.
208 *
209 * @param X the BigInteger to be used as input.
210 * @param n the public modulus.
211 * @param exp the exponent (e for encryption and verification,
212 * d for decryption and signing).
213 * @return the result of the computation.
214 */
215 public static BigInteger rsa(BigInteger X, BigInteger n, BigInteger exp)
216 {
217 return X.modPow(exp, n);
218 }
219 }