001: package org.bouncycastle.crypto.engines;
002:
003: import java.math.BigInteger;
004: import java.util.Vector;
005: import org.bouncycastle.util.Arrays;
006:
007: import org.bouncycastle.crypto.AsymmetricBlockCipher;
008: import org.bouncycastle.crypto.CipherParameters;
009: import org.bouncycastle.crypto.DataLengthException;
010: import org.bouncycastle.crypto.InvalidCipherTextException;
011: import org.bouncycastle.crypto.params.NaccacheSternKeyParameters;
012: import org.bouncycastle.crypto.params.NaccacheSternPrivateKeyParameters;
013:
014: /**
015: * NaccacheStern Engine. For details on this cipher, please see
016: * http://www.gemplus.com/smart/rd/publications/pdf/NS98pkcs.pdf
017: */
018: public class NaccacheSternEngine implements AsymmetricBlockCipher {
019: private boolean forEncryption;
020:
021: private NaccacheSternKeyParameters key;
022:
023: private Vector[] lookup = null;
024:
025: private boolean debug = false;
026:
027: private static BigInteger ZERO = BigInteger.valueOf(0);
028: private static BigInteger ONE = BigInteger.valueOf(1);
029:
030: /**
031: * Initializes this algorithm. Must be called before all other Functions.
032: *
033: * @see org.bouncycastle.crypto.AsymmetricBlockCipher#init(boolean,
034: * org.bouncycastle.crypto.CipherParameters)
035: */
036: public void init(boolean forEncryption, CipherParameters param) {
037: this .forEncryption = forEncryption;
038: key = (NaccacheSternKeyParameters) param;
039:
040: // construct lookup table for faster decryption if necessary
041: if (!this .forEncryption) {
042: if (debug) {
043: System.out.println("Constructing lookup Array");
044: }
045: NaccacheSternPrivateKeyParameters priv = (NaccacheSternPrivateKeyParameters) key;
046: Vector primes = priv.getSmallPrimes();
047: lookup = new Vector[primes.size()];
048: for (int i = 0; i < primes.size(); i++) {
049: BigInteger actualPrime = (BigInteger) primes
050: .elementAt(i);
051: int actualPrimeValue = actualPrime.intValue();
052:
053: lookup[i] = new Vector();
054: lookup[i].addElement(ONE);
055:
056: if (debug) {
057: System.out
058: .println("Constructing lookup ArrayList for "
059: + actualPrimeValue);
060: }
061:
062: BigInteger accJ = ZERO;
063:
064: for (int j = 1; j < actualPrimeValue; j++) {
065: accJ = accJ.add(priv.getPhi_n());
066: BigInteger comp = accJ.divide(actualPrime);
067: lookup[i].addElement(priv.getG().modPow(comp,
068: priv.getModulus()));
069: }
070: }
071: }
072: }
073:
074: public void setDebug(boolean debug) {
075: this .debug = debug;
076: }
077:
078: /**
079: * Returns the input block size of this algorithm.
080: *
081: * @see org.bouncycastle.crypto.AsymmetricBlockCipher#getInputBlockSize()
082: */
083: public int getInputBlockSize() {
084: if (forEncryption) {
085: // We can only encrypt values up to lowerSigmaBound
086: return (key.getLowerSigmaBound() + 7) / 8 - 1;
087: } else {
088: // We pad to modulus-size bytes for easier decryption.
089: return key.getModulus().toByteArray().length;
090: }
091: }
092:
093: /**
094: * Returns the output block size of this algorithm.
095: *
096: * @see org.bouncycastle.crypto.AsymmetricBlockCipher#getOutputBlockSize()
097: */
098: public int getOutputBlockSize() {
099: if (forEncryption) {
100: // encrypted Data is always padded up to modulus size
101: return key.getModulus().toByteArray().length;
102: } else {
103: // decrypted Data has upper limit lowerSigmaBound
104: return (key.getLowerSigmaBound() + 7) / 8 - 1;
105: }
106: }
107:
108: /**
109: * Process a single Block using the Naccache-Stern algorithm.
110: *
111: * @see org.bouncycastle.crypto.AsymmetricBlockCipher#processBlock(byte[],
112: * int, int)
113: */
114: public byte[] processBlock(byte[] in, int inOff, int len)
115: throws InvalidCipherTextException {
116: if (key == null) {
117: throw new IllegalStateException(
118: "NaccacheStern engine not initialised");
119: }
120: if (len > (getInputBlockSize() + 1)) {
121: throw new DataLengthException(
122: "input too large for Naccache-Stern cipher.\n");
123: }
124:
125: if (!forEncryption) {
126: // At decryption make sure that we receive padded data blocks
127: if (len < getInputBlockSize()) {
128: throw new InvalidCipherTextException(
129: "BlockLength does not match modulus for Naccache-Stern cipher.\n");
130: }
131: }
132:
133: byte[] block;
134:
135: if (inOff != 0 || len != in.length) {
136: block = new byte[len];
137: System.arraycopy(in, inOff, block, 0, len);
138: } else {
139: block = in;
140: }
141:
142: // transform input into BigInteger
143: BigInteger input = new BigInteger(1, block);
144: if (debug) {
145: System.out.println("input as BigInteger: " + input);
146: }
147: byte[] output;
148: if (forEncryption) {
149: output = encrypt(input);
150: } else {
151: Vector plain = new Vector();
152: NaccacheSternPrivateKeyParameters priv = (NaccacheSternPrivateKeyParameters) key;
153: Vector primes = priv.getSmallPrimes();
154: // Get Chinese Remainders of CipherText
155: for (int i = 0; i < primes.size(); i++) {
156: BigInteger exp = input.modPow(priv.getPhi_n().divide(
157: (BigInteger) primes.elementAt(i)), priv
158: .getModulus());
159: Vector al = lookup[i];
160: if (lookup[i].size() != ((BigInteger) primes
161: .elementAt(i)).intValue()) {
162: if (debug) {
163: System.out.println("Prime is "
164: + primes.elementAt(i)
165: + ", lookup table has size "
166: + al.size());
167: }
168: throw new InvalidCipherTextException(
169: "Error in lookup Array for "
170: + ((BigInteger) primes.elementAt(i))
171: .intValue()
172: + ": Size mismatch. Expected ArrayList with length "
173: + ((BigInteger) primes.elementAt(i))
174: .intValue()
175: + " but found ArrayList of length "
176: + lookup[i].size());
177: }
178: int lookedup = al.indexOf(exp);
179:
180: if (lookedup == -1) {
181: if (debug) {
182: System.out.println("Actual prime is "
183: + primes.elementAt(i));
184: System.out.println("Decrypted value is " + exp);
185:
186: System.out.println("LookupList for "
187: + primes.elementAt(i) + " with size "
188: + lookup[i].size() + " is: ");
189: for (int j = 0; j < lookup[i].size(); j++) {
190: System.out.println(lookup[i].elementAt(j));
191: }
192: }
193: throw new InvalidCipherTextException(
194: "Lookup failed");
195: }
196: plain.addElement(BigInteger.valueOf(lookedup));
197: }
198: BigInteger test = chineseRemainder(plain, primes);
199:
200: // Should not be used as an oracle, so reencrypt output to see
201: // if it corresponds to input
202:
203: // this breaks probabilisic encryption, so disable it. Anyway, we do
204: // use the first n primes for key generation, so it is pretty easy
205: // to guess them. But as stated in the paper, this is not a security
206: // breach. So we can just work with the correct sigma.
207:
208: // if (debug) {
209: // System.out.println("Decryption is " + test);
210: // }
211: // if ((key.getG().modPow(test, key.getModulus())).equals(input)) {
212: // output = test.toByteArray();
213: // } else {
214: // if(debug){
215: // System.out.println("Engine seems to be used as an oracle,
216: // returning null");
217: // }
218: // output = null;
219: // }
220:
221: output = test.toByteArray();
222:
223: }
224:
225: return output;
226: }
227:
228: /**
229: * Encrypts a BigInteger aka Plaintext with the public key.
230: *
231: * @param plain
232: * The BigInteger to encrypt
233: * @return The byte[] representation of the encrypted BigInteger (i.e.
234: * crypted.toByteArray())
235: */
236: public byte[] encrypt(BigInteger plain) {
237: // Always return modulus size values 0-padded at the beginning
238: // 0-padding at the beginning is correctly parsed by BigInteger :)
239: byte[] output = key.getModulus().toByteArray();
240: Arrays.fill(output, (byte) 0);
241: byte[] tmp = key.getG().modPow(plain, key.getModulus())
242: .toByteArray();
243: System.arraycopy(tmp, 0, output, output.length - tmp.length,
244: tmp.length);
245: if (debug) {
246: System.out.println("Encrypted value is: "
247: + new BigInteger(output));
248: }
249: return output;
250: }
251:
252: /**
253: * Adds the contents of two encrypted blocks mod sigma
254: *
255: * @param block1
256: * the first encrypted block
257: * @param block2
258: * the second encrypted block
259: * @return encrypt((block1 + block2) mod sigma)
260: * @throws InvalidCipherTextException
261: */
262: public byte[] addCryptedBlocks(byte[] block1, byte[] block2)
263: throws InvalidCipherTextException {
264: // check for correct blocksize
265: if (forEncryption) {
266: if ((block1.length > getOutputBlockSize())
267: || (block2.length > getOutputBlockSize())) {
268: throw new InvalidCipherTextException(
269: "BlockLength too large for simple addition.\n");
270: }
271: } else {
272: if ((block1.length > getInputBlockSize())
273: || (block2.length > getInputBlockSize())) {
274: throw new InvalidCipherTextException(
275: "BlockLength too large for simple addition.\n");
276: }
277: }
278:
279: // calculate resulting block
280: BigInteger m1Crypt = new BigInteger(1, block1);
281: BigInteger m2Crypt = new BigInteger(1, block2);
282: BigInteger m1m2Crypt = m1Crypt.multiply(m2Crypt);
283: m1m2Crypt = m1m2Crypt.mod(key.getModulus());
284: if (debug) {
285: System.out
286: .println("c(m1) as BigInteger:....... " + m1Crypt);
287: System.out
288: .println("c(m2) as BigInteger:....... " + m2Crypt);
289: System.out.println("c(m1)*c(m2)%n = c(m1+m2)%n: "
290: + m1m2Crypt);
291: }
292:
293: byte[] output = key.getModulus().toByteArray();
294: Arrays.fill(output, (byte) 0);
295: System.arraycopy(m1m2Crypt.toByteArray(), 0, output,
296: output.length - m1m2Crypt.toByteArray().length,
297: m1m2Crypt.toByteArray().length);
298:
299: return output;
300: }
301:
302: /**
303: * Convenience Method for data exchange with the cipher.
304: *
305: * Determines blocksize and splits data to blocksize.
306: *
307: * @param data the data to be processed
308: * @return the data after it went through the NaccacheSternEngine.
309: * @throws InvalidCipherTextException
310: */
311: public byte[] processData(byte[] data)
312: throws InvalidCipherTextException {
313: if (debug) {
314: System.out.println();
315: }
316: if (data.length > getInputBlockSize()) {
317: int inBlocksize = getInputBlockSize();
318: int outBlocksize = getOutputBlockSize();
319: if (debug) {
320: System.out.println("Input blocksize is: "
321: + inBlocksize + " bytes");
322: System.out.println("Output blocksize is: "
323: + outBlocksize + " bytes");
324: System.out.println("Data has length:.... "
325: + data.length + " bytes");
326: }
327: int datapos = 0;
328: int retpos = 0;
329: byte[] retval = new byte[(data.length / inBlocksize + 1)
330: * outBlocksize];
331: while (datapos < data.length) {
332: byte[] tmp;
333: if (datapos + inBlocksize < data.length) {
334: tmp = processBlock(data, datapos, inBlocksize);
335: datapos += inBlocksize;
336: } else {
337: tmp = processBlock(data, datapos, data.length
338: - datapos);
339: datapos += data.length - datapos;
340: }
341: if (debug) {
342: System.out.println("new datapos is " + datapos);
343: }
344: if (tmp != null) {
345: System
346: .arraycopy(tmp, 0, retval, retpos,
347: tmp.length);
348:
349: retpos += tmp.length;
350: } else {
351: if (debug) {
352: System.out.println("cipher returned null");
353: }
354: throw new InvalidCipherTextException(
355: "cipher returned null");
356: }
357: }
358: byte[] ret = new byte[retpos];
359: System.arraycopy(retval, 0, ret, 0, retpos);
360: if (debug) {
361: System.out
362: .println("returning " + ret.length + " bytes");
363: }
364: return ret;
365: } else {
366: if (debug) {
367: System.out
368: .println("data size is less then input block size, processing directly");
369: }
370: return processBlock(data, 0, data.length);
371: }
372: }
373:
374: /**
375: * Computes the integer x that is expressed through the given primes and the
376: * congruences with the chinese remainder theorem (CRT).
377: *
378: * @param congruences
379: * the congruences c_i
380: * @param primes
381: * the primes p_i
382: * @return an integer x for that x % p_i == c_i
383: */
384: private static BigInteger chineseRemainder(Vector congruences,
385: Vector primes) {
386: BigInteger retval = ZERO;
387: BigInteger all = ONE;
388: for (int i = 0; i < primes.size(); i++) {
389: all = all.multiply((BigInteger) primes.elementAt(i));
390: }
391: for (int i = 0; i < primes.size(); i++) {
392: BigInteger a = (BigInteger) primes.elementAt(i);
393: BigInteger b = all.divide(a);
394: BigInteger b_ = b.modInverse(a);
395: BigInteger tmp = b.multiply(b_);
396: tmp = tmp.multiply((BigInteger) congruences.elementAt(i));
397: retval = retval.add(tmp);
398: }
399:
400: return retval.mod(all);
401: }
402: }
|