1   /* $RCSfile: ISO9796Part1RSACodec.java,v $
2    * $Revision: 1.5 $
3    * $Date: 2003/06/22 02:28:39 $
4    * $Author: uwe_guenther $
5    * $State: Exp $
6    *
7    * Created on December 27, 2001 10:50 AM
8    *
9    * Copyright (C) 2001 Uwe Guenther <uwe@cscc.de>
10   *
11   * This file is part of the jhbci JCE-ServiceProvider. The jhbci JCE-
12   * ServiceProvider is a library, written in JavaTM, that should be 
13   * used in HBCI banking applications (clients and may be servers),
14   * to do cryptographic operations.
15   *
16   * The jhbci library is free software; you can redistribute it and/or
17   * modify it under the terms of the GNU Lesser General Public
18   * License as published by the Free Software Foundation; either
19   * version 2.1 of the License, or (at your option) any later version.
20   *
21   * The jhbci library is distributed in the hope that it will be useful,
22   * but WITHOUT ANY WARRANTY; without even the implied warranty of
23   * MERCHANTABILITY or FITNESS FOR A PARTICULAR PURPOSE.  See the GNU
24   * Lesser General Public License for more details.
25   *
26   * You should have received a copy of the GNU Lesser General Public
27   * License along with this library; if not, write to the Free Software
28   * Foundation, Inc., 59 Temple Place, Suite 330, Boston, MA  02111-1307  USA
29   *
30   */
31  
32  package de.cscc.crypto.provider;
33  
34  import java.math.BigInteger;
35  import java.security.InvalidKeyException;
36  import java.security.PrivateKey;
37  import java.security.PublicKey;
38  import java.security.interfaces.RSAKey;
39  import java.security.interfaces.RSAPrivateCrtKey;
40  import java.security.interfaces.RSAPrivateKey;
41  import java.security.interfaces.RSAPublicKey;
42  import java.util.Arrays;
43  import java.util.logging.Level;
44  import java.util.logging.Logger;
45  
46  import de.cscc.crypto.util.BigIntegerUtil;
47  import de.cscc.crypto.util.ByteUtil;
48  
49  /** 
50   * ISO9796Part1RSACodec Class.
51   *
52   * @author  <a href=mailto:uwe@cscc.de>Uwe G&uuml;nther</a>
53   *
54   * @version $Revision: 1.5 $
55   */
56  final class ISO9796Part1RSACodec implements Cloneable {
57  
58      /*
59       * First we declare all Stuff needed for logging with 
60       * java.util.logging.*
61       */
62  
63      /** The logger for this class.*/
64      private static final Logger log = 
65      Logger.getLogger(ISO9796Part1RSACodec.class.getName());
66          
67      
68      /** 
69       * The Shadow function S according to ISO9796-1:1991.
70       *
71       * <p>The shadow function S that will be used in the encoding and decoding
72       * operations according to ISO9796-1:1991/5.3 and 6.2
73       *
74       * <pre>
75       * Definition of Permutation PI:
76       * 
77       * µ     0123456789abcdef
78       * PI(µ) e358942f0db67ac1
79       * </pre>
80       *
81       * If nibble µ consists of the bits a4 a3 a2 a1, then under the 
82       * permutation PI, its image denoted by PI(µ) consists of the bits:
83       *
84       * <pre>
85       * a4^a2^a1^1 : a4^a3^a1^1 : a4^a3^a2^1 : a3^a2^a1
86       * </pre>
87       *
88       * If the byte m consists of the nibble µ2 µ1, then under shadow S,
89       * its image denoted by S(m) consists of the nibbles PI(µ2) PI(µ1).
90       */
91      private static final byte[] SHADOW = {
92          (byte) 0xee, (byte) 0xe3, (byte) 0xe5, (byte) 0xe8,
93          (byte) 0xe9, (byte) 0xe4, (byte) 0xe2, (byte) 0xef,
94          (byte) 0xe0, (byte) 0xed, (byte) 0xeb, (byte) 0xe6,
95          (byte) 0xe7, (byte) 0xea, (byte) 0xec, (byte) 0xe1,
96          (byte) 0x3e, (byte) 0x33, (byte) 0x35, (byte) 0x38,
97          (byte) 0x39, (byte) 0x34, (byte) 0x32, (byte) 0x3f,
98          (byte) 0x30, (byte) 0x3d, (byte) 0x3b, (byte) 0x36,
99          (byte) 0x37, (byte) 0x3a, (byte) 0x3c, (byte) 0x31,
100         (byte) 0x5e, (byte) 0x53, (byte) 0x55, (byte) 0x58,
101         (byte) 0x59, (byte) 0x54, (byte) 0x52, (byte) 0x5f,
102         (byte) 0x50, (byte) 0x5d, (byte) 0x5b, (byte) 0x56,
103         (byte) 0x57, (byte) 0x5a, (byte) 0x5c, (byte) 0x51,
104         (byte) 0x8e, (byte) 0x83, (byte) 0x85, (byte) 0x88,
105         (byte) 0x89, (byte) 0x84, (byte) 0x82, (byte) 0x8f,
106         (byte) 0x80, (byte) 0x8d, (byte) 0x8b, (byte) 0x86,
107         (byte) 0x87, (byte) 0x8a, (byte) 0x8c, (byte) 0x81,
108         (byte) 0x9e, (byte) 0x93, (byte) 0x95, (byte) 0x98,
109         (byte) 0x99, (byte) 0x94, (byte) 0x92, (byte) 0x9f,
110         (byte) 0x90, (byte) 0x9d, (byte) 0x9b, (byte) 0x96,
111         (byte) 0x97, (byte) 0x9a, (byte) 0x9c, (byte) 0x91,
112         (byte) 0x4e, (byte) 0x43, (byte) 0x45, (byte) 0x48,
113         (byte) 0x49, (byte) 0x44, (byte) 0x42, (byte) 0x4f,
114         (byte) 0x40, (byte) 0x4d, (byte) 0x4b, (byte) 0x46,
115         (byte) 0x47, (byte) 0x4a, (byte) 0x4c, (byte) 0x41,
116         (byte) 0x2e, (byte) 0x23, (byte) 0x25, (byte) 0x28,
117         (byte) 0x29, (byte) 0x24, (byte) 0x22, (byte) 0x2f,
118         (byte) 0x20, (byte) 0x2d, (byte) 0x2b, (byte) 0x26,
119         (byte) 0x27, (byte) 0x2a, (byte) 0x2c, (byte) 0x21,
120         (byte) 0xfe, (byte) 0xf3, (byte) 0xf5, (byte) 0xf8,
121         (byte) 0xf9, (byte) 0xf4, (byte) 0xf2, (byte) 0xff,
122         (byte) 0xf0, (byte) 0xfd, (byte) 0xfb, (byte) 0xf6,
123         (byte) 0xf7, (byte) 0xfa, (byte) 0xfc, (byte) 0xf1,
124         (byte) 0x0e, (byte) 0x03, (byte) 0x05, (byte) 0x08,
125         (byte) 0x09, (byte) 0x04, (byte) 0x02, (byte) 0x0f,
126         (byte) 0x00, (byte) 0x0d, (byte) 0x0b, (byte) 0x06,
127         (byte) 0x07, (byte) 0x0a, (byte) 0x0c, (byte) 0x01,
128         (byte) 0xde, (byte) 0xd3, (byte) 0xd5, (byte) 0xd8,
129         (byte) 0xd9, (byte) 0xd4, (byte) 0xd2, (byte) 0xdf,
130         (byte) 0xd0, (byte) 0xdd, (byte) 0xdb, (byte) 0xd6,
131         (byte) 0xd7, (byte) 0xda, (byte) 0xdc, (byte) 0xd1,
132         (byte) 0xbe, (byte) 0xb3, (byte) 0xb5, (byte) 0xb8,
133         (byte) 0xb9, (byte) 0xb4, (byte) 0xb2, (byte) 0xbf,
134         (byte) 0xb0, (byte) 0xbd, (byte) 0xbb, (byte) 0xb6,
135         (byte) 0xb7, (byte) 0xba, (byte) 0xbc, (byte) 0xb1,
136         (byte) 0x6e, (byte) 0x63, (byte) 0x65, (byte) 0x68,
137         (byte) 0x69, (byte) 0x64, (byte) 0x62, (byte) 0x6f,
138         (byte) 0x60, (byte) 0x6d, (byte) 0x6b, (byte) 0x66,
139         (byte) 0x67, (byte) 0x6a, (byte) 0x6c, (byte) 0x61,
140         (byte) 0x7e, (byte) 0x73, (byte) 0x75, (byte) 0x78,
141         (byte) 0x79, (byte) 0x74, (byte) 0x72, (byte) 0x7f,
142         (byte) 0x70, (byte) 0x7d, (byte) 0x7b, (byte) 0x76,
143         (byte) 0x77, (byte) 0x7a, (byte) 0x7c, (byte) 0x71,
144         (byte) 0xae, (byte) 0xa3, (byte) 0xa5, (byte) 0xa8,
145         (byte) 0xa9, (byte) 0xa4, (byte) 0xa2, (byte) 0xaf,
146         (byte) 0xa0, (byte) 0xad, (byte) 0xab, (byte) 0xa6,
147         (byte) 0xa7, (byte) 0xaa, (byte) 0xac, (byte) 0xa1,
148         (byte) 0xce, (byte) 0xc3, (byte) 0xc5, (byte) 0xc8,
149         (byte) 0xc9, (byte) 0xc4, (byte) 0xc2, (byte) 0xcf,
150         (byte) 0xc0, (byte) 0xcd, (byte) 0xcb, (byte) 0xc6,
151         (byte) 0xc7, (byte) 0xca, (byte) 0xcc, (byte) 0xc1,
152         (byte) 0x1e, (byte) 0x13, (byte) 0x15, (byte) 0x18,
153         (byte) 0x19, (byte) 0x14, (byte) 0x12, (byte) 0x1f,
154         (byte) 0x10, (byte) 0x1d, (byte) 0x1b, (byte) 0x16,
155         (byte) 0x17, (byte) 0x1a, (byte) 0x1c, (byte) 0x11
156     };   
157     
158     /** 
159      * The inverse PI function according to ISO9796-1:1991.
160      * See also the Shadow function S.
161      */
162     private static final byte[] PI_INV = {
163         (byte)0x08, (byte)0x0f, (byte)0x06, (byte)0x01, 
164         (byte)0x05, (byte)0x02, (byte)0x0b, (byte)0x0c, 
165         (byte)0x03, (byte)0x04, (byte)0x0d, (byte)0x0a, 
166         (byte)0x0e, (byte)0x09, (byte)0x00, (byte)0x07  
167     };    
168 
169     /** Frequently used BigIntegers */
170     private static final BigInteger ZERO    = BigInteger.ZERO;
171     private static final BigInteger ONE     = BigInteger.ONE;
172     private static final BigInteger TWO     = BigInteger.valueOf(2L);
173     private static final BigInteger THREE   = BigInteger.valueOf(3L);
174     private static final BigInteger FOUR    = BigInteger.valueOf(4L);
175     private static final BigInteger FIVE    = BigInteger.valueOf(5L);    
176     private static final BigInteger SIX     = BigInteger.valueOf(6L);
177     private static final BigInteger SEVEN   = BigInteger.valueOf(7L);
178     private static final BigInteger EIGHT   = BigInteger.valueOf(8L);
179     private static final BigInteger SIXTEEN = BigInteger.valueOf(16L);    
180    
181     
182     /** The object state variable. */
183     private State state = State.UNINITIALIZED;
184     
185     /** 
186      * Holds the either the key for encoding or for decoding.  
187      * 
188      * <p> This can be an RSAPublicKeyImpl, RSAPrivateKeyImpl or an
189      * RSAPrivateCrtKeyImpl from this provider.
190      */
191     private RSAKey key;
192     
193     /** Creates new ISO9796Part1RSACodec. */
194     ISO9796Part1RSACodec() {
195     }
196 
197     /**
198      * Creates and returns a copy of this object.  
199      *
200      * @return a clone of this instance.
201      * @throws CloneNotSupportedException  if the object's class does not
202      * support the <code>Cloneable</code> interface. Subclasses
203      * that override the <code>clone</code> method can also
204      * throw this exception to indicate that an instance cannot
205      * be cloned.
206      */    
207     public Object clone() throws CloneNotSupportedException {
208         //We copy only the object references, so we do a flat copy.
209         //This is ok, because the key is a immutable object and state
210         //is a typesafe enum.
211         return super.clone();
212     }
213     
214     /**
215      * Indicates whether some other object is "equal to" this one.
216      *
217      * @param   obj   the reference object with which to compare.
218      * @return  <code>true</code> if this object is the same as the obj
219      *         argument; <code>false</code> otherwise.
220      * @see     #hashCode()
221      * @see     java.util.Hashtable
222      */
223     public boolean equals(Object obj) {
224         //Only for performance.
225         if (this == obj) {
226             return true;
227         } 
228         
229         //If obj == null then instanceof returns false, see JLS 15.20.2
230         if (!(obj instanceof ISO9796Part1RSACodec)) {
231             return false;
232         }
233         
234         ISO9796Part1RSACodec other = (ISO9796Part1RSACodec)obj;
235         
236         if (this.state == State.UNINITIALIZED) {
237             //Check if the other key is also null.
238             return this.key == other.key &&  
239                    this.state == other.state;
240         } else { //(this.state != State.UNINITIALIZED)
241             return this.key.equals(other.key) &&
242                    this.state == other.state;
243         }
244     }
245     
246     /**
247      * Returns a hash code value for the object. 
248      *
249      * @return  a hash code value for this object.
250      * @see     java.lang.Object#equals(java.lang.Object)
251      * @see     java.util.Hashtable
252      */
253     public int hashCode() {
254         //If key is null we can't invoke hashCode().
255         if (this.state == State.UNINITIALIZED) {
256             int result = 17;
257             result = 37*result + this.state.hashCode();            
258             return result;
259         //So key isn't null and we can invoke hashCode().
260         } else {
261             int result = 17;
262             result = 37*result + this.key.hashCode();
263             result = 37*result + this.state.hashCode();                        
264             return result;
265         }
266     }    
267     
268     /**
269      * Returns a string representation of the object. 
270      *
271      * @return  a string representation of the object.
272      */    
273     public String toString() {
274         return "[ISO9796Part1RSACodec - state: " + this.state + "]";
275     }    
276     
277     /**
278      * Initializes this codec object with the specified public key
279      * for encoding operations. We accept only RSAPublicKey or
280      * RSAPrivateCrtKey from this provider.
281      *
282      * @param privateKey the private key that will be used for 
283      * encoding operations.
284      * @throws NullPointerException if privateKey is null.
285      * @throws InvalidKeyException if privateKey is not a RSAPrivateKey or a
286      * RSAPrivateCrtKey from this provider.
287      */
288     void initEncode(PrivateKey privateKey) throws InvalidKeyException {
289         if (privateKey == null) {
290             throw new NullPointerException("Parameter privateKey is null.");
291         }
292         if (privateKey instanceof RSAPrivateCrtKeyImpl) {
293             this.key = (RSAKey) privateKey;
294         } else if (privateKey instanceof RSAPrivateKeyImpl) {
295             this.key = (RSAKey) privateKey;
296         } else {
297             throw new InvalidKeyException("Inapproiate Key.");
298         }   
299         this.state = State.ENCODE;
300     }
301     
302     /**
303      * Initializes this codec object with the specified private key
304      * for decoding operatins. We accept only RSAPublicKey from this provider.
305      *
306      * @param publicKey the public key that will be used for
307      * decoding operations.
308      * @throws NullPointerException if publicKey is null.
309      * @throws InvalidKeyException if publicKey is not a RSAPublicKey from 
310      * this provider.
311      */    
312     void initDecode(PublicKey publicKey) throws InvalidKeyException {
313         if (publicKey == null) {
314             throw new NullPointerException("Parameter publicKey is null.");
315         }
316         if (publicKey instanceof RSAPublicKeyImpl) {
317             this.key = (RSAKey) publicKey;
318         } else {
319             throw new InvalidKeyException("Inapproiate Key.");
320         }        
321         this.state = State.DECODE;
322     }    
323 
324     /**
325      * ISO9796-1 Message Encoding with RSA-Encryption.
326      *
327      * <p>This implementation is fully ISO9796-1 compatible.
328      *
329      * @param bitStringMessage the bit string that should be formated according
330      * to ISO9796-1 with usage of RSA for the sigma function.
331      * @param publicExponentEven should be true if the 'publicExponent' of the
332      * RSAPublicKey is a even number or false if the 'publicExponent' of the
333      * RSAPublicKey is odd.
334      * @return the with RSA signed ISO9796-1 formated representation of 
335      * the message. 
336      * @throws NullPointerException if bitStringMessage is null.
337      * @throws IllegalArgumentException if the 'messageBitLength' isn't be at 
338      * most 8 times the largest integer less than or equal to (ks+3)/16. 
339      * This means 'z' should less than or equal to (ks+3)/16. Where 'ks' is the 
340      * modulus bit length aubtract by one.
341      * @throws IllegalStateException if this Codec object isn't initialized
342      * for encoding.
343      */    
344     ISO9796Part1BitString encodeMessage(
345     ISO9796Part1BitString bitStringMessage, boolean publicExponentEven) {
346         //Debug method entry.
347         if (log.isLoggable(Level.FINER)) {
348             log.finer("Entering encodeMessage(<bitStringMessage="+
349             bitStringMessage+"> ,publicExponentEven=<"+publicExponentEven+">).");
350         }
351         
352         //Debug Member usage.
353         if (log.isLoggable(Level.FINEST)) {
354             log.finest("Will use member <key=" + this.key + ">.");
355             log.finest("We are in <state=" + this.state + ">.");
356         }
357         
358         
359         
360         //////
361         //
362         // Pre-Conditions check
363         //
364         //////
365         
366         if (this.state != State.ENCODE) {
367             IllegalStateException e = new IllegalStateException(
368             "The ISO9796Part1RSACodec is not in the ENCODE state.");
369             
370             if (log.isLoggable(Level.FINER)) {
371                 log.finer("Throwing IllegalSateException, because (<state="+ 
372                 this.state+"> != State.ENCODE). Exception: " + e);
373             }
374             
375             throw e;
376         }
377         if (bitStringMessage == null) {
378             NullPointerException e = new NullPointerException(
379             "Parameter bitStringMessage is null.");
380             
381             if (log.isLoggable(Level.FINER)) {
382                 log.finer("Throwing NullPointerExeption, because " +
383                 "(<bitStringMessage="+bitStringMessage+"> == null). " + 
384                 "Exception: " + e);
385             }
386             
387             throw e;
388         }
389 
390         
391         
392         //////
393         //
394         // Message Padding
395         //
396         //////
397 
398         //'ks' is the length of the signatur bit string in bits. 'ks' is 
399         //defined in ISO9796-1:1991/3 as the length of the modulus in bit ('k')
400         //minus one (ks = k - 1).        
401         final int ks = this.key.getModulus().bitLength() - 1;  
402         
403         if (log.isLoggable(Level.FINEST)) {
404             log.finest("Have calculated <ks="+ks+ 
405             "> = <key.getModulus().bitLength()="+ 
406             this.key.getModulus().bitLength()+"> - 1." );
407         }
408         
409         //'messageBitLength' is the length in bits of the message that should be 
410         //encoded according to ISO9796-1WithRSA.
411         final int messageBitLength = bitStringMessage.getBitLength();
412         
413         if (log.isLoggable(Level.FINEST)) {
414             log.finest("Have set <messageBitLength="+messageBitLength+ 
415             "> = <bitStringMessage.getBitLength()="+ 
416             bitStringMessage.getBitLength()+">.");
417         }        
418         
419         //'z' is the number of bytes in the padded message, denoted as 'mp'. If
420         //the 'messageBitLength' is not a multiple of 8 the 'message' will be 
421         //padded with 0 to 7 zero bits in the padded messsage 'mp'.
422         final int z = (messageBitLength + 7) / 8;
423         
424         if (log.isLoggable(Level.FINEST)) {
425             log.finest("Have calculated <z=" + z + "> = (<messageBitLength="+
426             messageBitLength+"> + 7) / 8.");
427         }        
428         
429         //Check if the 'messageBitLength' is be at most 8 times the largest 
430         //integer less than or equal to (ks+3)/16. This means 'z' should less 
431         //than or equal to (ks+3)/16. See (ISO9796-1:1991/5.1) for more details.
432         if ((z * 16) > (ks + 3)) {
433             IllegalArgumentException e = new IllegalArgumentException(
434             "Parameter bitStringMessage is to large for the modulus bit " + 
435             "length of the given private key.");
436             
437             if (log.isLoggable(Level.FINER)) {
438                 log.finer("Throwing IllegalArgumentException, because " + 
439                 "((<z="+z+"> * 16) > (<ks="+ks+"> + 3)) ." + 
440                 "Exception: " + e);
441             }
442             
443             throw e;            
444         }                
445         
446         //Create the new byte array 'mp' with a length of 'z' bytes.
447         final byte[] mp = new byte[z];
448         
449         if (log.isLoggable(Level.FINEST)) {
450             log.finest("Have created <mp"+ByteUtil.toHex(mp)+
451             "> = new byte[<z="+z+">]");
452         }
453         
454         //The 'message' that should be encoded according to ISO9796-1WithRSA.
455         final byte[] message = bitStringMessage.getBitString();        
456         
457         if (log.isLoggable(Level.FINEST)) {
458             log.finest("Have set <message=" + ByteUtil.toHex(message) + 
459             "> = <bitStringMessage.getBitString()=" + 
460             ByteUtil.toHex(bitStringMessage.getBitString()) + ">.");
461         }                
462         
463         //Copy the 'message' into 'mp' where all bytes are right-justified.
464         System.arraycopy(message, message.length - mp.length, mp, 0, mp.length);
465         
466         if (log.isLoggable(Level.FINEST)) {
467             log.finest("Have copied <message=" + ByteUtil.toHex(message) + 
468             "> into <mp=" + ByteUtil.toHex(mp) + "> aligned to the right.");
469         }                
470         
471         //'r' is the number of padded zeros plus one. 
472         //'r' is thus valued from 1 to 8.
473         final int r = (8 - messageBitLength % 8) % 8 + 1;        
474         
475         if (log.isLoggable(Level.FINEST)) {
476             log.finest("Have calculated <r="+r+
477             "> = (8 - <messageBitLength="+messageBitLength+"> % 8) % 8 + 1.");
478         }
479         
480         //Pad 'mp' on the left side (set the unused 'r-1 bits' to zero).
481         //mp[0] &= 0xff >>> ((8 - (messageBitLength % 8)) % 8);
482         mp[0] &= 0xff >>> (r - 1);
483         
484         if (log.isLoggable(Level.FINEST)) {
485             log.finest("Have padded mp on the left side: <mp="+
486             ByteUtil.toHex(mp)+"> &= 0xff >>> (<r="+r+"> - 1).");
487         }
488         
489         //Debug 'mp'.
490         if (log.isLoggable(Level.FINER)) {
491             log.finer("Final result of <mp=" + ByteUtil.toHex(mp) + ">.");
492         }
493         
494         
495         
496         //////
497         //
498         // Extend Message and add Redundancy.
499         //
500         //////
501 
502         //The extended message with redundancy have to create in to steps:
503         //1. Create the extended message 'me' by repeating the 'z' bytes of 'mp', 
504         //   as many times as necessary, in order and concatenated to the left, 
505         //   until forming a string of t bytes.
506         //2. Create the extende message with redundancy 'mr' by interleaving the 
507         //   't' bytes of 'me' in odd positions and 't' bytes of redundancy in 
508         //   even positions. Altered by index 'r', the least significant 
509         //   nibble of the '2z-th byte' of 'mr' codes the message length by 
510         //   its value in its position.
511         //For performance and memory reasons we haven't an extra 'me'. So we 
512         //create 'mp' with all 'me'-like operations defined in ISO9796-1:1991.        
513         
514         //'t' is the least integer, such that a string of '2t bytes' includes at
515         //least 'ks-1 bits'.
516         final int t = (ks + 14) / 16 ;
517         
518         if (log.isLoggable(Level.FINEST)) {
519             log.finest("Have calculated <t="+t+"> = (<ks="+ks+"> + 14) / 16.");
520         }        
521         
522         //Create mp with a length of '2t bytes'
523         final byte[] mr = new byte[2 * t];
524         
525         if (log.isLoggable(Level.FINEST)) {
526             log.finest("Have created <mr"+ByteUtil.toHex(mr)+
527             "> = new byte[2 * <t="+t+">]");
528         }
529         
530         //Extend and interleave the padded message mp.
531         for(int i = 1; i <= t ; i++) {
532             //odd position in 'mr' -> (2i-1) -> 't' byte of 'me'
533             mr[2*t - (2*i-1)] = mp[z-(((i-1) % z) + 1)];
534             //even -> (2i)   -> 't' byte of redundancy with the help of SHADOW.
535             mr[2*t - (2*i)] = SHADOW[mp[z-(((i-1) % z) + 1)] & 0xff];
536         }     
537         
538         if (log.isLoggable(Level.FINEST)) {
539             log.finest("Have extended and interleaved <mr"+ByteUtil.toHex(mr)+
540             ">.");
541         }        
542         
543         //The '2z-th byte' of 'mr' equals the exclusive-or of index 'r' with the 
544         //shadow of the 'z-th byte' of 'me'.        
545         mr[2*t - (2*z)] ^= (byte) r;
546 
547         if (log.isLoggable(Level.FINEST)) {
548             log.finest("Have xored r to the 2*z-th byte of mr: "+
549             "<mr[<2*<t="+t+"> - (2*<z="+z+">)="+(2*t - (2*z))+">]="+
550             ByteUtil.toHex(mr[2*t - (2*z)])+"> ^= (byte) <r="+r+">.");
551         }        
552         
553         //Debug mr.
554         if (log.isLoggable(Level.FINER)) {
555             log.finer("Final result of <mr=" + ByteUtil.toHex(mr) + ">.");
556         }    
557         
558         
559         //////
560         //
561         // Truncation and forcing.
562         //
563         //////
564         
565         //'ir' is a bit string of ks bits, this means that if you want to place 
566         //the bit string 'ir' in a byte array, the byte array have to at least a
567         //length of ((ks + 7) / 8) bytes.
568         final byte[] ir = new byte [(ks + 7) / 8];
569         
570         if (log.isLoggable(Level.FINEST)) {
571             log.finest("Have created <ir"+ByteUtil.toHex(ir)+
572             "> = new byte[(<ks="+ks+"> + 7) / 8].");
573         }        
574         
575         //Copy 'mr' into 'ir'. 
576         //We have to distinguish between two cases:
577         //1. The number of bytes in ir is greater than or equal to the
578         //   number of bytes in mr.
579         //2. The number of bytes in ir is less than the number of bytes in mr.
580         //This differentiation is necessary, because the number of bytes in mr
581         //is a multiple of 16 and the number of bytes in ir is multiple of 8.
582         if (ir.length >= mr.length) {
583            System.arraycopy(mr, 0, ir, ir.length - mr.length, mr.length); 
584         } else { //(ir.length < mr.length)
585             System.arraycopy(mr, mr.length - ir.length, ir, 0, ir.length);
586         }
587         
588         if (log.isLoggable(Level.FINEST)) {
589             log.finest("Have copied <mr=" + ByteUtil.toHex(mr) + 
590             "> into <ir=" + ByteUtil.toHex(ir) + "> aligned to the right.");
591         }                        
592         
593         //Truncation of 'ir'
594         //1. set most significant bit (MSB) ks to 1
595         ir[0] |= 0x01 << ((ks + 7) % 8);     
596         
597         if (log.isLoggable(Level.FINEST)) {
598             log.finest("Have set the most significant bit (MSB) <ks="+ks+
599             "> to 1: <ir[0]="+ByteUtil.toHex(ir[0])+"> |= 0x01 << ((<ks="+ks+
600             "> + 7) % 8).");
601         }
602         
603         //Truncation of 'ir'
604         //2. add padding zero bit(s). These are this bits that are more
605         //significant than the ks-th bit.
606         ir[0] &= 0xff >>> ir.length * 8 - ks;
607         
608         if (log.isLoggable(Level.FINEST)) {
609             log.finest("Have padded the bits that are more significant than " +
610             "the <ks="+ks+">-th bit to zero: <ir[0]="+ByteUtil.toHex(ir[0])+
611             "> &= 0xff >>> <ir.length="+ir.length+"> * 8 - <ks="+ks+">.");
612         }        
613         
614         //Forcing of 'ir'
615         //Means that the least significant byte in import is replaced
616         //by the following procedure:
617         //If (µ2||µ1) is the least significant byte of 'mr', then the least
618         //significant byte of 'ir' shall be (µ1||6). 
619         ir[ir.length - 1] = (byte) ((mr[mr.length - 1] << 4) | 0x06);
620         
621         if (log.isLoggable(Level.FINEST)) {
622             log.finest("Have forced the least significant byte of ir: " +
623             "<ir[<ir.length="+ir.length+"> - 1]="+ByteUtil.toHex(ir[ir.length - 1])+
624             "> = (byte) ((<mr[<mr.length="+mr.length+"> - 1]="+ 
625             ByteUtil.toHex(mr[mr.length - 1])+"> << 4) | 0x06).");
626         }
627         
628         //Debug 'ir'.
629         if (log.isLoggable(Level.FINER)) {
630             log.finer("Final result of <ir=" + ByteUtil.toHex(ir) + ">.");
631         }       
632 
633         
634 
635         //////
636         //
637         // Produce the Signature
638         //
639         //////
640         
641         //Get 'modulus'
642         final BigInteger modulus = this.key.getModulus();        
643 
644         if (log.isLoggable(Level.FINEST)) {
645             log.finest("Have set <modulus="+modulus+
646             "> = <key.getModulus()="+this.key.getModulus()+">.");
647         }
648         
649         //Convert 'ir' to the BigInteger representation of 'ir' -
650         //denoted as the represantive element 'irAsNumber'.            
651         final BigInteger irAsNumber = new BigInteger(1, ir);        
652 
653         if (log.isLoggable(Level.FINEST)) {
654             log.finest("Have converted ir to irAsNumber:  <irAsNumber="+
655             irAsNumber+"> = <new BigInteger(1, <ir="+ByteUtil.toHex(ir)+">).");
656         }        
657         
658         //The representative Element of 'ir' with respect to modulus
659         //is denoted by 'rr'.
660         BigInteger rr;
661         
662         //public exponent is even
663         if (publicExponentEven) { 
664             //Calculate the jacobi symbol of (ir|modulus)
665             int jacobiSymbol = jacobi(irAsNumber, modulus);
666             
667             if (log.isLoggable(Level.FINEST)) {
668                 log.finest("Modulus is even.");
669                 log.finest("Have set <jacobiSymbol="+jacobiSymbol+">");
670             }
671             
672             //jacobiSymbol of (irAsNumber|modulus) = 1
673             if( jacobiSymbol == 1) {
674                 //Set the representative element 'rr' = 'ir'.
675                 rr = irAsNumber;
676                 
677                 if (log.isLoggable(Level.FINEST)) {
678                     log.finest("Have set <rr="+rr+"> = <irAsNumber="+
679                     irAsNumber+">.");
680                 }
681                 
682             //jacobySymbol of (irAsNumber|modulus) = -1
683             } else if (jacobiSymbol == -1) {
684                 //Set the representative element 'rr' = 'ir' / 2.
685                 rr = irAsNumber.divide(TWO);
686                 
687                 if (log.isLoggable(Level.FINEST)) {
688                     log.finest("Have set <rr="+rr+"> = <irAsNumber="+
689                     irAsNumber+"> / 2.");
690                 }                
691 
692             //Should not happen.
693             } else {
694                 IllegalStateException e = new IllegalStateException(
695                 "The jacobi symbol (ir|modulus) isn't equal to 1 or to -1.");
696                 
697                 if (log.isLoggable(Level.FINER)) {
698                     log.finer("Throwing IllegalSateException, because " +
699                     "<jacobySymbol="+jacobiSymbol+
700                     "> isn't equal to 1 or to -1. Exception: " + e);
701                 }
702                 
703                 throw e;
704             }
705 
706         // public exponent is odd    
707         } else { 
708             //Convert 'ir' to the BigInteger representation of 'rr'.
709             rr = irAsNumber;
710             
711             if (log.isLoggable(Level.FINEST)) {
712                 log.finest("Modulus is odd.");
713                 log.finest("Have set <rr="+rr+"> = <irAsNumber="+
714                 irAsNumber+">.");
715             }            
716         }
717         
718         //Debug 'rr'.
719         if (log.isLoggable(Level.FINER)) {
720             log.finer("Final result of <rr=" + 
721             ByteUtil.toHex(BigIntegerUtil.toUnsignedByteArray(rr)) + ">.");
722         }    
723             
724         //Chinese remainder theorem RSA decryption according to RSA PKCS1.
725         //Here it will be used to _encrypt_ the representative element 'rr' with
726         //help of the signers private key.        
727         BigInteger cipherText;
728         if (this.key instanceof RSAPrivateCrtKey) {
729             final BigInteger primeP =
730             ((RSAPrivateCrtKey) this.key).getPrimeP();
731             final BigInteger primeQ =
732             ((RSAPrivateCrtKey) this.key).getPrimeQ();
733             final BigInteger primeExponentP =
734             ((RSAPrivateCrtKey) this.key).getPrimeExponentP();
735             final BigInteger primeExponentQ =
736             ((RSAPrivateCrtKey) this.key).getPrimeExponentQ();
737             final BigInteger crtCoefficient =
738             ((RSAPrivateCrtKey) this.key).getCrtCoefficient();
739             //Calc Signature
740             final BigInteger cipherTextOne = 
741             rr.modPow(primeExponentP, primeP);
742             final BigInteger cipherTextTwo = 
743             rr.modPow(primeExponentQ, primeQ);
744             final BigInteger h =
745             cipherTextOne.subtract(cipherTextTwo).multiply(crtCoefficient).mod(primeP);
746             cipherText = primeQ.multiply(h).add(cipherTextTwo);
747         
748             if (log.isLoggable(Level.FINEST)) {
749                 log.finest("Have calulated <cipherText="+cipherText+
750                 "> with RSAPrivateCrtKey <key="+this.key+">.");
751             }
752             
753         //Original RSA decryption according to Rivest, Shamir and Adelmann.
754         //Here it will be used to _encrypt_ the representative element 'rr' with
755         //help of the signers private key.
756         } else if (this.key instanceof RSAPrivateKey) {
757             final BigInteger privateExponent =
758             ((RSAPrivateKey) this.key).getPrivateExponent();
759             //Calc Signature
760             cipherText = rr.modPow(privateExponent, modulus);
761 
762             if (log.isLoggable(Level.FINEST)) {
763                 log.finest("Have calulated <cipherText="+cipherText+
764                 "> with RSAPrivateKey <key="+this.key+">.");
765             }            
766             
767         //We are wrong... (default case - shouldn't really happen!) If we 
768         //are ditching here, there are something wrong with initialization.                    
769         } else {
770             IllegalStateException e = new IllegalStateException(
771             "ISO9796Part1Codec contains inappropriate Key.");   
772             
773             if (log.isLoggable(Level.FINER)) {
774                 log.finer("Throwing IllegalSateException, Exception: " + e);
775             }
776                 
777             throw e;            
778         }
779         
780         // sigma = min(rr^s mod n, n - (rr^s mod n)) 
781         final BigInteger sigmaAsNumber = 
782         cipherText.min(modulus.subtract(cipherText));
783         
784         if (log.isLoggable(Level.FINEST)) {
785             log.finest("Have set <sigmaAsNumber="+sigmaAsNumber+
786             "> = min(cipherText, modulus-cipherText).");
787         }
788         
789         //Convert sigmaAsNumber to an unsigned byte array.
790         final byte[] sigma = 
791         BigIntegerUtil.toUnsignedByteArray(sigmaAsNumber);
792         
793         //Debug 'sigma'.
794         if (log.isLoggable(Level.FINER)) {
795             log.finer("Final result of <sigma=" + ByteUtil.toHex(sigma) + ">.");
796             //added to detect our first bug ;-) 05/30/2002
797             log.finer("Final length of <sigma.length=" + sigma.length + ">.");
798             log.finer("Final bit length of sigma is <ks="+ks+"> bit.");
799         }
800         
801         //Create 'bitStringSignature' from 'sigma' and its length in bits 'ks' 
802         //as ISO9796Part1BitString.        
803         ISO9796Part1BitString bitStringSignature = 
804         new ISO9796Part1BitString(sigma, ks);
805         
806         if (log.isLoggable(Level.FINER)) {
807             log.finer("Return from encodeMessage(...) with <bitStringSignature="+
808             bitStringSignature+">.");
809         }
810         
811         //Return the bitStringSignature.
812         return bitStringSignature;                    
813     }
814     
815     /**
816      * ISO9796-1 RSA-Signature Decoding with Message Recovery.
817      *
818      * <p> This is the inverse operation of 
819      * encodeMessage(ISO97696Part1RSACodec, boolean)
820      *
821      * @param bitStringSignature the Signature as ISO9796Part1BitString with a
822      * bitLength of k-1 bits. Where k is the bitLength of the public key 
823      * modulus.
824      * @return the recoverd message as ISO9796Part1Message or null if the 
825      * signature is rejected.
826      * throws NullPointerException if bitStringSignature is null.
827      * @throws IllegalStateException if this Codec object isn't initialized
828      * for decoding.
829      */    
830     ISO9796Part1BitString decodeSignature(
831     ISO9796Part1BitString bitStringSignature) {
832         //Debug method entry.
833         if (log.isLoggable(Level.FINER)) {
834             log.finer("Entering decodeMessage(<bitStringSignature="+
835             bitStringSignature+">.");
836         }
837         
838         //Debug Member usage.
839         if (log.isLoggable(Level.FINEST)) {
840             log.finest("Will use member <key=" + this.key + ">.");
841             log.finest("We are in <state=" + this.state + ">.");
842         }        
843         
844         
845         
846         //////
847         //
848         // Pre-Conditions check
849         //
850         //////
851 
852         if (this.state != State.DECODE) {
853             IllegalStateException e = new IllegalStateException(
854             "The ISO9796Part1RSACodec is not in the DECODE state.");
855             
856             if (log.isLoggable(Level.FINER)) {
857                 log.finer("Throwing IllegalSateException, because (<state="+ 
858                 this.state+"> != State.DECODE). Exception: " + e);
859             }
860             
861             throw e;
862         }        
863         if (bitStringSignature == null) {
864             NullPointerException e = new NullPointerException(
865             "Parameter bitStringSignature is null.");
866             
867             if (log.isLoggable(Level.FINER)) {
868                 log.finer("Throwing NullPointerException, because " +
869                 "<bitStringSignature="+bitStringSignature+">. " + 
870                 "Exception: " + e);
871             }            
872             
873             throw e;
874         }
875         
876 
877         
878         //////
879         //
880         // RSA Verification function (A.5) and Signature opening(6.1)
881         //
882         //////
883         
884         //Get 'modulus'
885         final BigInteger modulus = this.key.getModulus();
886         
887         if (log.isLoggable(Level.FINEST)) {
888             log.finest("Have set <modulus="+modulus+
889             "> = <key.getModulus()="+this.key.getModulus()+">.");
890         }        
891         
892         //Get 'sigma'.
893         final byte[] sigma = bitStringSignature.getBitString();
894         
895         //Debug 'sigma'.
896         if (log.isLoggable(Level.FINER)) {
897             log.finer("Recovered result of <sigma=" + ByteUtil.toHex(sigma) + ">.");
898         }        
899         
900         //Convert the signature 'sigma' to the BigInteger representation of the 
901         //signature 'sigma' - denoted as 'sigmaAsNumber'.        
902         final BigInteger sigmaAsNumber = new BigInteger(1, sigma);
903         
904         if (log.isLoggable(Level.FINEST)) {
905             log.finest("Have converted <sigmaAsNumber="+sigmaAsNumber+
906             "> = new BigInteger(1, <sigma="+ByteUtil.toHex(sigma)+">).");
907         }
908         
909         //if (sigmaAsNumber >= n/2)
910         if (sigmaAsNumber.compareTo(modulus.divide(TWO)) >= 0) {
911             log.finer(
912             "Return from decodeSignature(...). " +
913             "Reject Signature! " +
914             "Signature is not a positive integer less than modulus/2.");
915             
916             //reject signature.
917             return null;
918         }        
919         
920         //Setup RSA public exponent.
921         final BigInteger publicExponent = 
922         ((RSAPublicKey) this.key).getPublicExponent();
923         
924         if (log.isLoggable(Level.FINEST)) {
925             log.finest("Have set <publicExponent="+publicExponent+
926             "> = <((RSAPublicKey) key).getPublicExponent()="+
927             ((RSAPublicKey) this.key).getPublicExponent()+">");
928         }        
929         
930         //Do RSA encryption operation, according to Rivest, Shamir and Adelmann.
931         //Here it will be used to _decrypt_ the the signature 'sigma' with
932         //help of the signers public key. The result will be the resulting
933         //integer 'is'        
934         final BigInteger is = (sigmaAsNumber.modPow(publicExponent, modulus));
935         
936         if (log.isLoggable(Level.FINEST)) {
937             log.finest("Have decrypted <is="+is+"> = <sigmaAsNumber="+
938             sigmaAsNumber+">^<publicExponent="+publicExponent+"> mod <modulus="+
939             modulus+">.");
940         }
941         
942         //
943         //In the following code section, we do recover the intermediate
944         //integer ir, first as a number an then we will it convert to a
945         //byte array.
946         //
947         
948         //The recovered intermediate integer 'ir'
949         BigInteger irAsNumber;
950         
951         //public exponent is even
952         if (publicExponent.mod(TWO).equals(ZERO)) {
953             if (log.isLoggable(Level.FINEST)) {
954                 log.finest("Public exponent is even.");
955             }
956             
957             //if (is % 16 == 6)
958             if (is.mod(SIXTEEN).equals(SIX)) {
959                 if (log.isLoggable(Level.FINEST)) {
960                     log.finest("is mod 16 is congruent to 6.");                
961                 }                
962                 
963                 //ir = is
964                 irAsNumber = is;
965                 
966                 if (log.isLoggable(Level.FINEST)) {
967                     log.finest("Have set <irAsNumber="+irAsNumber+
968                     "> = <is="+is+">.");                
969                 }
970             
971             //if ((modulus - is) % 16 == 6)    
972             } else if (modulus.subtract(is).mod(SIXTEEN).equals(SIX)) {
973                 if (log.isLoggable(Level.FINEST)) {
974                     log.finest("(modulus - is) mod 16 is congruent to 6.");                
975                 }                                
976                 
977                 //ir = modulus - is
978                 irAsNumber = modulus.subtract(is);
979             
980                 if (log.isLoggable(Level.FINEST)) {
981                     log.finest("Have calculated <irAsNumber="+irAsNumber+
982                     "> = <modulus="+modulus+"> - <is="+is+">."); 
983                 }
984                            
985             
986             //if (is % 8 == 3)
987             } else if (is.mod(EIGHT).equals(THREE)) {
988                 if (log.isLoggable(Level.FINEST)) {
989                     log.finest("is mod 8 is congruent to 3.");                
990                 }                                
991                 
992                 //ir = 2is
993                 irAsNumber = is.multiply(TWO);
994                 
995                 if (log.isLoggable(Level.FINEST)) {
996                     log.finest("Have calculated <irAsNumber="+irAsNumber+
997                     "> = 2 * <is="+is+">.");
998                 }                
999             
1000            //if ((modulus - is) % 8 == 3)    
1001            } else if (modulus.subtract(is).mod(EIGHT).equals(THREE)) {
1002                if (log.isLoggable(Level.FINEST)) {
1003                    log.finest("(modulus - is) mod 8 is congruent to 3.");                
1004                }                
1005                
1006                //ir = 2(modulus - is)
1007                irAsNumber = modulus.subtract(is).multiply(TWO);
1008            
1009                if (log.isLoggable(Level.FINEST)) {
1010                    log.finest("Have calculated <irAsNumber="+irAsNumber+
1011                    "> = 2 * (<modulus="+modulus+"> - <is="+is+">).");
1012                }                                
1013                
1014            //is or modulus-is is not congruent to 3 mod 8     
1015            } else {
1016                log.finer(
1017                "Return from decodeSignature(...). " +
1018                "Reject Signature! " +
1019                "is or (modulus - is) is not congruent to 3 mod 8 or to " + 
1020                "6 mod 16.");                
1021                
1022                //reject signature.
1023                return null;        
1024            }           
1025            
1026        //public exponent is odd
1027        } else {
1028            if (log.isLoggable(Level.FINEST)) {
1029                log.finest("Public exponent is odd.");
1030            }            
1031            
1032            //if (is % 16 == 6)
1033            if (is.mod(SIXTEEN).equals(SIX)) {
1034                if (log.isLoggable(Level.FINEST)) {
1035                    log.finest("is mod 16 is congruent to 6.");                
1036                }                
1037                
1038                //ir = is
1039                irAsNumber = is;
1040                
1041                if (log.isLoggable(Level.FINEST)) {
1042                    log.finest("Have set <irAsNumber="+irAsNumber+
1043                    "> = <is="+is+">.");                
1044                }
1045            
1046            //if ((modulus - is) % 16 == 6)    
1047            } else if (modulus.subtract(is).mod(SIXTEEN).equals(SIX)) {
1048                if (log.isLoggable(Level.FINEST)) {
1049                    log.finest("(modulus - is) mod 16 is congruent to 6.");                
1050                }                                
1051                
1052                //ir = modulus - is
1053                irAsNumber = modulus.subtract(is);
1054            
1055                if (log.isLoggable(Level.FINEST)) {
1056                    log.finest("Have calculated <irAsNumber="+irAsNumber+
1057                    "> = <modulus="+modulus+"> - <is="+is+">."); 
1058                }
1059                
1060            //is or modulus-is is not congruent to 6 mod 16     
1061            } else {
1062                log.finer(
1063                "Return from decodeSignature(...). " +
1064                "Reject Signature! " +
1065                "is or (modulus - is) is not congruent to 6 mod 16.");                
1066                
1067                //reject signature.
1068                return null;            
1069            }
1070        }
1071        
1072        //'k' is the length of the 'modulus' in bits.
1073        final int k = modulus.bitLength();
1074        
1075        if (log.isLoggable(Level.FINEST)) {
1076                log.finest("Have set <k="+k+"> = <modulus.bitLength()="+
1077                modulus.bitLength()+">.");                
1078        }                        
1079        
1080        //The lower bound for 'ir'
1081        final BigInteger lowerBound = TWO.pow(k - 2);
1082        
1083        //The upper bound for 'ir'
1084        final BigInteger upperBound = TWO.pow(k - 1).subtract(ONE);
1085        
1086        //if (ir < lowerBound)
1087        if (irAsNumber.compareTo(lowerBound) < 0) {
1088            log.finer(
1089            "Return from decodeSignature(...). " +
1090            "Reject Signature! " +
1091            "<irAsNumber="+irAsNumber+"> is less than of 2^(k-2).");                
1092                
1093            //reject signature.
1094            return null;
1095        }
1096        
1097        //if (import > upperBound)
1098        if (irAsNumber.compareTo(upperBound) > 0) {
1099            log.finer(
1100            "Return from decodeSignature(...). " +
1101            "Reject Signature! " +
1102            "<irAsNumber="+irAsNumber+"> is greater than 2^(k-1)-1.");                
1103                
1104            //reject signature.
1105            return null;
1106        }     
1107        
1108        //Convert the BigInteger representation of 'ir', denoted as 
1109        //'irAsNumber', ot the byte array representation of 'ir', denoted 
1110        //as 'ir'.
1111        byte[] ir = BigIntegerUtil.toUnsignedByteArray(irAsNumber);
1112        
1113        if (log.isLoggable(Level.FINEST)) {
1114            log.finest("Have converted <ir="+ByteUtil.toHex(ir)+
1115            "> = BigIntegerUtil.toUnsignedByteArray(<irAsNumber="+
1116            irAsNumber+">).");
1117        }        
1118        
1119        //We dont have to check if 'ir' is a bit string of 'ks' bits, because
1120        //we do this with the BigInteger bound checkeing, where we check above
1121        //if irAsNumber is in the range between 2^(k-2) to 2^(k-1)-1 
1122        //inclusively.
1123        
1124        //Check if the least significant nibble is valued to 6
1125        if ((ir[ir.length - 1] & 0x0f) != 0x06) {
1126            //LSN isn't 6
1127            log.finer(
1128            "Return from decodeSignature(...). " +
1129            "Reject Signature! " +
1130            "Least significant nibble of ir isn't 6: <(ir[<ir.length="+
1131            ir.length+"> - 1] & 0x0f)="+(ir[ir.length - 1] & 0x0f)+">.");
1132                
1133            //reject signature.
1134            return null;            
1135        }     
1136        
1137        //Debug 'ir'.
1138        if (log.isLoggable(Level.FINER)) {
1139            log.finer("Recovered result of <ir="+ByteUtil.toHex(ir)+">.");
1140        }
1141        
1142        
1143        
1144        //////
1145        //
1146        // Message recovery
1147        //
1148        //////
1149        
1150        //'ks' the length of the signature 'sigma' in bits. 
1151        final int ks = k - 1;
1152        
1153        if (log.isLoggable(Level.FINEST)) {
1154            log.finest("Have calculated <ks="+ks+"> = <k"+k+"> - 1.");
1155        }
1156        
1157        //'t' is the least integer, such that a string of '2t bytes' includes at
1158        //least 'ks-1 bits'.
1159        final int t = (ks + 14) / 16 ;
1160        
1161        if (log.isLoggable(Level.FINEST)) {
1162            log.finest("Have calculated <t="+t+"> = (<ks="+ks+"> + 14) / 16.");
1163        }        
1164        
1165        //Create 'mr' with a length of '2t bytes'
1166        final byte[] mr = new byte[2 * t];
1167        
1168        if (log.isLoggable(Level.FINEST)) {
1169            log.finest("Have created <mr"+ByteUtil.toHex(mr)+
1170            "> = new byte[2 * <t="+t+">]");
1171        }        
1172        
1173        //Copy 'ir' into 'mr'. We have to distinguish between two cases:
1174        //1. The number of bytes in ir is greater than or equal to the
1175        //   number of bytes in mr.
1176        //2. The number of bytes in ir is less than the number of bytes in mr.
1177        //This differentiation is necessary, because the number of bytes in mr
1178        //is a multiple of 16 and the number of bytes in ir is multiple of 8.
1179        if (ir.length >= mr.length) {
1180           System.arraycopy(ir, ir.length - mr.length, mr, 0, mr.length); 
1181        } else { //(ir.length < mr.length)
1182            System.arraycopy(ir, 0, mr, mr.length - ir.length, ir.length);
1183        }        
1184        
1185        if (log.isLoggable(Level.FINEST)) {
1186            log.finest("Have copied <ir=" + ByteUtil.toHex(ir) + 
1187            "> into <mr=" + ByteUtil.toHex(mr) + "> aligned to the right.");
1188        }
1189        
1190        //Mask out (pad) all 16t - (ks - 1) bits to the left as padding bits.
1191        //This is the reverse operation to the truncation operation.
1192        if ((ks - 1) % 16 < 8) {
1193            if ((ks - 1) % 8 == 0) {
1194                mr[0] &= 0xff;                
1195                if (log.isLoggable(Level.FINEST)) {
1196                    log.finest("Have set <mr[0]="+ByteUtil.toHex(mr[0])+
1197                    "> &= 0xff.");
1198                }                
1199            } else {
1200                mr[0] &= 0x00;
1201                if (log.isLoggable(Level.FINEST)) {
1202                    log.finest("Have set <mr[0]="+ByteUtil.toHex(mr[0])+
1203                    "> &= 0x00.");
1204                }                
1205            }
1206            mr[1] &= 0xff >>> ((8 - (ks - 1) % 8) % 8);
1207            if (log.isLoggable(Level.FINEST)) {
1208                log.finest("Have set <mr[1]="+ByteUtil.toHex(mr[1])+
1209                "> &= <0xff >>> ((8 - (<ks="+ks+"> - 1) % 8) % 8)="+
1210                ByteUtil.toHex((byte) (0xff >>> ((8 - (ks - 1) % 8) % 8)))+">.");
1211            }            
1212        } else { //((ks - 1) % 16 >= 8)
1213            mr[0] &= 0xff >>> (8 - (ks - 1) % 8);
1214            if (log.isLoggable(Level.FINEST)) {
1215                log.finest("Have set <mr[0]="+ByteUtil.toHex(mr[0])+
1216                "> &= <0xff >>> (8 - (<ks="+ks+"> - 1) % 8)="+
1217                ByteUtil.toHex((byte) (0xff >>> (8 - (ks - 1) % 8)))+">.");
1218            }            
1219        } 
1220        
1221
1222        
1223        //This is the reverse operation to the forcing operation.
1224        mr[mr.length - 1] = 
1225        (byte) ((PI_INV[(mr[mr.length - 2] >>> 4) & 0x0f] << 4) |
1226                ((mr[mr.length - 1] >>> 4) & 0x0f));
1227        
1228        if (log.isLoggable(Level.FINEST)) {
1229            log.finest("Do reverse operation of forcing to <mr[<mr.length="+
1230            mr.length+"> - 1]="+ByteUtil.toHex(mr[mr.length - 1])+">.");
1231        }
1232        
1233        //Debug 'mr'.
1234        if (log.isLoggable(Level.FINER)) {
1235            log.finer("Recovered result of <mr="+ByteUtil.toHex(mr)+">.");
1236        }    
1237        
1238        //Declare and initialize the flag tSumsAreNull, the number z and 
1239        //the index r.
1240        boolean tSumsAreNull = true;
1241        int z = 0;
1242        int r = 0;
1243        
1244        //Search for z and r in mr, while looking for the first non null sum.
1245        for (int i = 1; i <= t; i++) {
1246            //Debug m_2i and S(m_2i-1)
1247            byte sumA = mr[mr.length - (2 * i)];
1248            byte sumB = SHADOW[mr[mr.length - ((2 * i) - 1)] & 0xff];
1249
1250            //Compute the 't'-th 'sum'.
1251            int sum = mr[mr.length - (2 * i)] ^ 
1252            SHADOW[mr[mr.length - ((2 * i) - 1)] & 0xff];
1253            
1254            if (log.isLoggable(Level.FINEST)) {
1255                log.finest("Look for first non null sum: index <i="+i+"> <sum="+
1256                sum+"> = <mr["+(mr.length - (2 * i))+"]="+ByteUtil.toHex(sumA)+
1257                "> ^ <mr["+(mr.length - ((2 * i) - 1))+"]="+ByteUtil.toHex(sumB)+
1258                ">.");             
1259            }
1260            
1261            //We found the first non null 'sum'.
1262            if (sum != 0) {
1263                if(log.isLoggable(Level.FINEST)) {
1264                    log.finest("Found first non null sum!");
1265                }
1266                //Tell the flag that we have found the first non null sum.
1267                tSumsAreNull = false;
1268                //Number 'z' is recovered as the position  of the first 
1269                //non null 'sum'.
1270                z = i;
1271                if(log.isLoggable(Level.FINEST)) {
1272                    log.finest("Have set <z="+z+"> = <i="+i+">.");
1273                }
1274                //Index 'r' is recovered as the value  of the least significant
1275                //nibble of the first non null 'sum'.
1276                r = sum & 0x0f;
1277                if(log.isLoggable(Level.FINEST)) {
1278                    log.finest("Have calculated <r="+r+"> = <sum="+sum+
1279                    "> & 0x0f.");
1280                }                
1281                break;
1282            }
1283        }
1284        
1285        //The signature sigma shall be rejected if  the t sums are null.
1286        if (tSumsAreNull) {
1287            //reject signature
1288            log.finer(
1289            "Return from decodeSignature(...). " +
1290            "Reject Signature! " +
1291            "All <t="+t+"> sums are null.");
1292                
1293            //reject signature.
1294            return null;       
1295        }
1296        
1297        //The signature sigma shall be rejected if  if index r is not
1298        //valued from 1 to 8.
1299        if ( r < 1 || r > 8) {
1300            log.finer(
1301            "Return from decodeSignature(...). " +
1302            "Reject Signature! " +
1303            "<r="+r+"> is out of range. r have to be (1 <= r <= 8).");
1304                
1305            //reject signature.
1306            return null;       
1307        }
1308        
1309        //Create 'mp' with a length of 'z' bytes.
1310        final byte[] mp = new byte[z];
1311        
1312        if (log.isLoggable(Level.FINEST)) {
1313            log.finest("Have created <mp"+ByteUtil.toHex(mp)+
1314            "> = new byte[<z="+z+">]");
1315        }        
1316        
1317        //The recovered padded message 'mp' is the string of the 'z' least 
1318        //significant bytes in odd position in 'mr'
1319        for (int i = 1; i <= z; i++) {
1320            mp[mp.length - i] = mr[mr.length - ((2 * i) - 1)];
1321        }
1322        log.finest("mp: " + ByteUtil.toHex(mp));
1323        
1324        //Check the padded zero bits in 'mp'.
1325        if (((mp[0] & (0xff << (9 - r))) & 0xff) != 0x00) {
1326            //The 'r' - 1  most significant bits of 'mp' are not zero.
1327            log.finer(
1328            "Return from decodeSignature(...). " +
1329            "Reject Signature! " +
1330            "(<(<mp[0]="+ByteUtil.toHex(mp[0])+"> & (0xff << (9 - <r="+r+">)))="+
1331            ByteUtil.toHex((byte) (mp[0] & (0xff << (9 - r))))+"> != 0x00).");                
1332                
1333            //reject signature.
1334            return null;
1335        }
1336        
1337        //Debug 'ir'.
1338        if (log.isLoggable(Level.FINER)) {
1339            log.finer("Recovered result of <mp="+ByteUtil.toHex(mp)+">.");
1340        }       
1341
1342        
1343        
1344        //////
1345        //
1346        // Redundancy checking
1347        //
1348        //////
1349
1350        //The signature 'sigma' shall only be accepted if and only if the 
1351        //'ks'-1 least significant bits of 'mr' are equal to the 'ks'-1 least
1352        //significant bits of another extended message with redundancy 
1353        //'anotherMr' computed from the recovered padded message 'mp'.
1354        
1355        //The another extended message with redundancy have to created in to 
1356        //steps:
1357        //1. Create another extended message 'anotherMe' by repeating the 
1358        //   'z' bytes of 'mp', as many times as necessary, in order and 
1359        //   concatenated to the left, until forming a string of t bytes.
1360        //2. Create another extende message with redundancy 'anotherMr' by 
1361        //   interleaving the 't' bytes of 'anotherMe' in odd positions and 
1362        //   't' bytes of redundancy in even positions. Altered by index 'r', 
1363        //   the least significant nibble of the '2z-th byte' of 'anotherMr' 
1364        //   codes the message length by its value in its position.
1365        //For performance and memory reasons we haven't an extra 'anotherMe'. 
1366        //So we create 'anotherMp' with all 'anotherMe'-like operations defined
1367        //in ISO9796-1:1991.        
1368        
1369        //Create anotherMr with a length of '2t bytes'
1370        final byte[] anotherMr = new byte[2 * t];
1371        
1372        if (log.isLoggable(Level.FINEST)) {
1373            log.finest("Have created <anotherMr"+ByteUtil.toHex(anotherMr)+
1374            "> = new byte[2 * <t="+t+">]");
1375        }        
1376        
1377        //Extend and interleave the padded message mp.
1378        for(int i = 1; i <= t ; i++) {
1379            //odd position in 'anotherMr' -> (2i-1) -> 't' byte of 'me'
1380            anotherMr[2*t - (2*i-1)] = mp[z-(((i-1) % z) + 1)];
1381            //even -> (2i)   -> 't' byte of redundancy with the help of SHADOW.
1382            anotherMr[2*t - (2*i)] = SHADOW[mp[z-(((i-1) % z) + 1)] & 0xff];
1383        }     
1384        
1385        if (log.isLoggable(Level.FINEST)) {
1386            log.finest("Have extended and interleaved <anotherMr"+
1387            ByteUtil.toHex(anotherMr)+">.");
1388        }        
1389        
1390        //The '2z-th byte' of 'anotherMr' equals the exclusive-or of index 'r'
1391        //with the shadow of the 'z-th byte' of 'anotherMe'.        
1392        anotherMr[2*t - (2*z)] ^= (byte) r;
1393        
1394        if (log.isLoggable(Level.FINEST)) {
1395            log.finest("Have xored r to the 2*z-th byte of anothermr: "+
1396            "<anotherMr[<2*<t="+t+"> - (2*<z="+z+">)="+(2*t - (2*z))+">]="+
1397            ByteUtil.toHex(anotherMr[2*t - (2*z)])+"> ^= (byte) <r="+r+">.");
1398        }        
1399        
1400        //Mask out (pad) all 16t - (ks - 1) bits to the left as padding bits.
1401        //This is the reverse operation to the truncation operation.
1402        if ((ks - 1) % 16 < 8) {
1403            if ((ks - 1) % 8 == 0) {
1404                anotherMr[0] &= 0xff;
1405                if (log.isLoggable(Level.FINEST)) {
1406                    log.finest("Have set <anotherMr[0]="+
1407                    ByteUtil.toHex(anotherMr[0])+"> &= 0xff."); 
1408                }
1409            } else {
1410                anotherMr[0] &= 0x00;
1411                if (log.isLoggable(Level.FINEST)) {
1412                    log.finest("Have set <anotherMr[0]="+
1413                    ByteUtil.toHex(anotherMr[0])+"> &= 0x00.");                
1414                }
1415            }
1416            anotherMr[1] &= 0xff >>> ((8 - (ks - 1) % 8) % 8);
1417            if (log.isLoggable(Level.FINEST)) {
1418                log.finest("Have set <anotherMr[1]="+
1419                ByteUtil.toHex(anotherMr[1])+"> &= <0xff >>> ((8 - (<ks="+ks+
1420                "> - 1) % 8) % 8)="+
1421                ByteUtil.toHex((byte) (0xff >>> ((8 - (ks - 1) % 8) % 8)))+">.");
1422            }            
1423        } else { //((ks - 1) % 16 >= 8)
1424            anotherMr[0] &= 0xff >>> (8 - (ks - 1) % 8);
1425            if (log.isLoggable(Level.FINEST)) {
1426                log.finest("Have set <anotherMr[0]="+ByteUtil.toHex(anotherMr[0])+
1427                "> &= <0xff >>> (8 - (<ks="+ks+"> - 1) % 8)="+
1428                ByteUtil.toHex((byte) (0xff >>> (8 - (ks - 1) % 8)))+">.");
1429            }            
1430        }         
1431        
1432        //Debug anotherMr.
1433        if (log.isLoggable(Level.FINER)) {
1434            log.finer("Final result of <anotherMr=" + ByteUtil.toHex(anotherMr) + 
1435            ">.");
1436        }   
1437
1438        //Verify if 'mr' and 'anotherMr' are the same. On step further we 
1439        //masked the 16t - (ks - 1) padding bits so we compare now only the
1440        //ks - 1 least significant bits in 'mr' with the ks - 1 least 
1441        //significant bits in 'anotherMr'.
1442        if (Arrays.equals(mr, anotherMr) == false) {
1443            //ks - 1 least significant bits in 'mr' are different to the ks - 1
1444            //least significant bits in 'anotherMr'.
1445            log.finer(
1446            "Return from decodeSignature(...). " +
1447            "Reject Signature! " +
1448            "<ks="+ks+"> - 1 least significant bits in <mr="+ByteUtil.toHex(mr)+
1449            "> are different to the <ks="+ks+" - 1 least significant bits in " +
1450            "<anotherMr="+ByteUtil.toHex(anotherMr)+">.");                
1451                
1452            //reject signature.
1453            return null;
1454        }
1455
1456        if (log.isLoggable(Level.FINEST)) {
1457            log.finest("<mr="+ByteUtil.toHex(mr)+
1458            "> is equal to <anotherMr="+ByteUtil.toHex(anotherMr)+">.");
1459        }
1460        
1461        //Calculate the 'message' bit string length 'messageBitLength'.
1462        int messageBitLength = (z * 8) - (r - 1);
1463        
1464        if (log.isLoggable(Level.FINEST)) {
1465            log.finest("Have calculated <messageBitLength="+messageBitLength+
1466            "> = (<z="+z+"> * 8) - (<r"+r+"> - 1).");
1467        }
1468        
1469        //Create the bitStringMessage object.
1470        ISO9796Part1BitString bitStringMessage = 
1471        new ISO9796Part1BitString(mp, messageBitLength);        
1472        
1473        if (log.isLoggable(Level.FINER)) {
1474            log.finer("Return from decodeMessage(...) with <bitStringMessage="+
1475            bitStringMessage+">.");
1476        }        
1477        
1478        //We are right so we return the recovered message.
1479        return bitStringMessage;
1480    }    
1481    
1482    /** 
1483     * This method calculates the jacobi symbol (a|n) from the two BigIntegers 
1484     * a and n. The two numbers have to satisfy the following preconditions:
1485     * <pre>
1486     * 1. n is odd
1487     * 2. 3 <= n
1488     * 3. 0 <= a < n
1489     * </pre>
1490     *
1491     * <p> The pseudo code for this method was taken from the great book 
1492     * "Handbook of Applied Cryptography by A.Menezes, P. van Oorschot and 
1493     * S. Vanstone. See Page 73, Algorithm 2.149 for details
1494     *
1495     * <p> You can find it in the Internet at:
1496     * http://www.cacr.math.uwaterloo.ca/hac/about/chap2.pdf
1497     * 
1498     * <p> Sample C code can be found at:
1499     * ftp://ftp.mindspring.com/users/pate/crypto/chap02/jacobi.c
1500     * 
1501     * @param a param of the jacobi symbol
1502     * @param n param of the jacobi symbol
1503     * @return the jacobi symbol (a|n), that will be -1 or 0 or 1.
1504     * @throws NullPointerException if a or n is null.
1505     * @throws IllegalArgumentException if n is even or (n &lt; 3), further
1506     * if a and n don't satisfies the condition (0 &lt;= a &lt; n)
1507     */
1508    private int jacobi(BigInteger a, BigInteger n) {
1509        if (a == null) {
1510            throw new NullPointerException("Parameter 'a' is null.");
1511        }
1512        if (n == null) {
1513            throw new NullPointerException("Parameter 'n' is null.");
1514        }     
1515        //(n < 3)
1516        if (n.compareTo(THREE) < 0) {
1517            throw new IllegalArgumentException("Parameter 'n' is less than 3.");
1518        }
1519        //(a < 0)
1520        if (a.compareTo(ZERO) < 0) {
1521            throw new IllegalArgumentException(
1522            "Parameter 'a' is less than zero.");
1523        }
1524        //(n <= a)
1525        if (n.compareTo(a) <= 0) {
1526            throw new IllegalArgumentException("Parameter 'n' is less than " +
1527            "or equal to parameter 'a'.");
1528        }
1529        // n should be odd
1530        if (n.mod(TWO).equals(BigInteger.ZERO)) {
1531            throw new IllegalArgumentException("Parameter 'n' is a even " +
1532            "number but 'n' should odd.");
1533        }
1534        
1535        return jacobiWorker(a, n);
1536    }
1537     
1538    /**
1539     * This method calculates the jacobi symbol (a|n) from the two BigIntegers 
1540     * a and n. Without prcondition check. Only the jacobi method should invoke
1541     * this method. We have this done because the recursive invokation of the
1542     * jacobiWorker. We have sepparated these two methods because, we 
1543     * do in jacobi(..) the exception checking for the initial entry.
1544     *
1545     * @param a param of the jacobi symbol
1546     * @param n param of the jacobi symbol
1547     * @return the jacobi symbol (a|n), that will be -1 or 0 or 1.
1548     */
1549    private int jacobiWorker(BigInteger a, BigInteger n) {
1550        
1551        //if (a == 0) {
1552        if (a.equals(ZERO)) {
1553            return 0;
1554        }
1555        
1556        //if (a == 1) {
1557        if (a.equals(ONE)) {
1558            return 1;
1559        }
1560        
1561        BigInteger b = a;
1562        BigInteger e = ZERO;
1563        //while ((b & 1) == 0) { // while (b is even)
1564        while (b.mod(TWO).equals(ZERO)) {
1565            //b >>>= 1;
1566            b = b.shiftRight(1);
1567            //e++;
1568            e = e.add(ONE);
1569        }
1570        BigInteger a1 = b;
1571        
1572        //m = n % 8;
1573        BigInteger m = n.mod(EIGHT);
1574        
1575        int s = 1;
1576        //if ((e & 1) == 0) {
1577        if (e.mod(TWO).equals(ZERO)) {
1578            s = 1;
1579        //} else if (m == 1 || m == 7) {
1580        } else if (m.equals(ONE) || m.equals(SEVEN)) {
1581            s = 1;
1582        //} else if (m == 3 || m == 5) {
1583        } else if (m.equals(THREE) || m.equals(FIVE)) {
1584            s = -1;
1585        }
1586        
1587        //if (n % 4 == 3 && a1 % 4 == 3) {
1588        if (n.mod(FOUR).equals(THREE) && a1.mod(FOUR).equals(THREE)) {
1589            s = -s;
1590        }
1591        
1592        BigInteger n1;        
1593        //if (a1 != 1) {
1594        if (a1.equals(ONE) == false) {
1595            //n1 = n % a1; 
1596            n1 = n.mod(a1);
1597        } else  {
1598            //n1 = 1;
1599            n1 = ONE;
1600        }
1601        
1602        return s * jacobiWorker(n1, a1);
1603    }
1604
1605    /** Type safe enum for the enclosing class object state. */
1606    private final static class State {
1607        /** Name odf the state. */
1608        private final String name;
1609        
1610        /** Constructor need only to called within this class. */
1611        private State(String name) {
1612            this.name = name;
1613        }
1614        
1615        /**                                                                                              z
1616         * Returns a string representation of the object. 
1617         *
1618         * @return  a string representation of the object.
1619         */
1620        public String toString() {
1621            return this.name;
1622        }
1623        
1624        /** State constante if the enclosing class isn't initialized. */
1625        private static final State UNINITIALIZED = 
1626        new State("UNINITIALIZED");
1627        
1628        /** State constante if the enclossing class is in Sign mode. */
1629        private static final State ENCODE = new State("ENCODE");
1630        
1631        /** State constante if the enclossing class is in Verify mode. */        
1632        private static final State DECODE = new State("DECODE");
1633    }         
1634}
1635