1 /**
  2  * @namespace RSA Public Key cryptography
  3  * @author Anonymized
  4  * @description
  5  * <p>An implementation of PKCS#1 v2.1.</p>
  6  * <p>The main difference with other PKCS#1 implementations
  7  * is the format of the keys. Instead of using ASN.1 for
  8  * encoding, the keys are stored in an equivalent JSON object.
  9  * For a public key, the fields are 'n' for the modulus and
 10  * 'e' for the public exponent. In addition, a private key must
 11  * contain the CRT values 'dmp1', 'dmq1', 'p', 'q' and 'iqmp'
 12  * (the private exponent 'd' is not required because it is not
 13  * used for decryption; using BigInteger it is easy to compute
 14  * 'dmp1', 'dmq1' and 'iqmp' from 'd', 'p' and 'q').</p>
 15  * <p>Use the following PHP script (requires the openssl extension)
 16  * to convert a PKCS#1 key to JSON:</p>
 17  * <pre>#!/usr/bin/env php
 18  * <?
 19  * if(count($argv)<2) die("Usage: {$argv[0]} file.pem\n");
 20  * $f = "file://{$argv[1]}";
 21  * if(!($k = openssl_pkey_get_private($f)))
 22  *  dir("Failed to import private key {$argv[1]}.\n");
 23  * $d = openssl_pkey_get_details($k);
 24  * $pk = $d['rsa'];
 25  * foreach($pk as $p=>$v) $pk[$p] = bin2hex($v);
 26  * echo json_encode($pk)."\n";</pre>
 27  * @requires BigInteger
 28  * @requires encoding
 29  * @requires hashing
 30  */
 31  var rsa =
 32  {
 33 /** Label of OAEP encryption, an ASCII string empty by default.
 34   * Can be of any length since it will be hash using rsa.encryption_hash
 35   */
 36   label: '',
 37 
 38 /** Salt of PSS signature, an ASCII string empty by default.
 39   * The max length is n-h-2 where n is the modulus size in bytes and h the
 40   * size in bytes of the output of the hash function.
 41   */
 42   salt: '',
 43 
 44 /** Hash function to use for OAEP label (hashing.sha256 by default) */
 45   encryption_hash: hashing.sha256,
 46 
 47 /** Hash function to use for MGF function (hashing.sha256 by default) */
 48   mgf_hash: hashing.sha256,
 49 
 50 /** Hash function to use for PSS signature (hashing.sha256 by default) */
 51   signature_hash: hashing.sha256,
 52 
 53 /** If something fails, this code provides information about the error.
 54   * <table width="100%"><tr><th>Code</th><th>Description</th></tr>
 55   * <tr><th>0</td><td>No error.</td></tr>
 56   * <tr><th>1</td><td>Message is too long for the modulus.</td></tr>
 57   * <tr><th>2</td><td>Invalid length of the input to decrypt or verify.</td></tr>
 58   * <tr><th>3</td><td>Top byte/bit is not zero after decryption/verification.</td></tr>
 59   * <tr><th>4</td><td>Incorrect padding of encrypted/signature data.</td></tr>
 60   * <tr><th>5</td><td>Bad label of OAEP encryption.</td></tr>
 61   * <tr><th>6</td><td>PSS salt is too long for modulus.</td></tr>
 62   * <tr><th>7</td><td>Invalid PSS padding byte in PSS signature.</td></tr>
 63   * </table> */
 64   error_code: 0,
 65 
 66 /** RSAES-OAEP-ENCRYPT encryption.
 67   * @param {string} m Message to encode, an ASCII string
 68   * @param {publicKey} pub Public key
 69   * @returns {string} Hex string representing the encrypted message
 70   */
 71   encrypt: function(message, pub)
 72   {
 73    var m = encoding.astr2hstr(message)+'', Ns = pub.n+'', Es = pub.e+'',
 74        n = pub.n.length>>1, l = m.length>>1, h = this.encryption_hash,
 75        N = BigInteger.create(pub.n), E = BigInteger.create(pub.e),
 76        i = 0, DB = '', pad = '', sm = '', hs = h.size,
 77        seed = encoding.astr2hstr(h.hash(message+this.label));
 78 
 79    if(n-2*hs-2 < l){this.error_code = 1; return '' }
 80    for(i=0; i < n-2*hs-2-l; i++) pad += '00';
 81    DB = encoding.astr2hstr(h.hash(this.label)) + pad + '01' + m;
 82 
 83    // Mask
 84    pad = this.MGF(seed, n-hs-1);
 85    DB = BigInteger.toString(BigInteger.xor(BigInteger.create(DB),BigInteger.create(pad)));
 86    if(!!(DB.length&1)) DB = '0'+DB;
 87 
 88    // Final message
 89    sm = BigInteger.toString(BigInteger.xor(BigInteger.create(seed), BigInteger.create(this.MGF(DB, hs))));
 90    DB = BigInteger.toString(BigInteger.expMod(BigInteger.create(sm+DB), E, N));
 91    if(!!(DB.length&1)) DB = '0'+DB;
 92 
 93    this.error_code = 0;
 94    return DB;
 95   },
 96 
 97 /** RSADP/RSASP1 - Computes m^d mod n using CRT coefficients.
 98   * @private
 99   * @param {string} message Hex-encoded message
100   * @param {privateKey} priv Private key object
101   * @returns {string} Hex string representing m^d mod n
102   */
103   _private: function(message, priv)
104   {
105    var C = BigInteger.create(message), dP = BigInteger.create(priv.dmp1),
106        dQ = BigInteger.create(priv.dmq1), P = BigInteger.create(priv.p),
107        Q = BigInteger.create(priv.q), qInv = BigInteger.create(priv.iqmp),
108        M = BigInteger.create("0");
109 
110    // CRT decryption
111    dP = BigInteger.expMod(C,dP,P); // m1 = c ^ dP mod p
112    dQ = BigInteger.expMod(C,dQ,Q);// m2 = c ^ dQ mod q
113    BigInteger.subTo(dP, dQ, M);
114    BigInteger.multiplyTo(M, qInv, C);
115    BigInteger.multiplyTo(Q, BigInteger.mod(C,P), M); // h = qInv * (m1 - m2) mod p
116    BigInteger.subTo(dQ, BigInteger.negate(M), C); // m = m2 + h * q
117    return BigInteger.toString(C);
118   },
119 
120 /** RSAES-OAEP-DECRYPT decryption.
121   * @param {string} message Hex string containing the encrypted data
122   * @param {privateKey} priv Private Key
123   * @returns {string} ASCII string representing the original message, or an empty string if decryption failed.
124   */
125   decrypt: function(message, priv)
126   {
127    var m = message+'', n = (priv.n+'').length>>1, l = m.length>>1,
128        f = false, DB = '', sm = '', pad = '', i = 0,
129        h = this.encryption_hash, hs = h.size;
130 
131    if(n != l){ this.error_code = 2; return "" }
132    DB = this._private(m,priv);
133    for(i = priv.n.length-DB.length; i>0; i--) DB = '0'+DB;
134 
135    // Parsing and unmasking
136    for(i=0; i < DB.length; i++)
137    {
138     if(i<2){ if(DB[i] != '0'){ this.error_code = 3; return ''}}
139     else if(i < 2*(hs+1)) sm += DB[i];
140     else pad += DB[i];
141    }
142 
143    DB = this.MGF(pad, hs);
144    sm = BigInteger.toString(BigInteger.xor(BigInteger.create(sm), BigInteger.create(DB)));
145    DB = this.MGF(sm, n-hs-1);
146    DB = BigInteger.toString(BigInteger.xor(BigInteger.create(pad),BigInteger.create(DB)));
147    if(!!(DB.length&1)) DB='0'+DB;
148 
149    // Unpadding
150    m = ''; f = false; sm = '';
151    for(i=0; i < DB.length; i++)
152    {
153     if(i < 2*hs){sm += DB[i]; continue;}
154     pad = DB[i];
155     if(f) m += pad;
156     else
157     {
158      if(pad == "1"){ if(!(i&1)) break; else f = true; }
159      else if(pad != "0") break;
160     }
161    }
162    if(!sm){this.error_code = 4; return "" }
163    if(sm != encoding.astr2hstr(h.hash(this.label))){ this.error_code = 5; return "" }
164 
165    this.error_code = 0;
166    return encoding.hstr2astr(m);
167   },
168 
169 /** RSASSA-PSS-SIGN signature using rsa.signature_hash.
170   * @param {string} message ASCII string containing the data to sign
171   * @param {privateKey} priv Private Key
172   * @returns {string} Hex string representing a PSS signature for the data
173   */
174   sign: function(message, priv)
175   {
176    var h = this.signature_hash, hs = h.size, m = h.hash(message+''),
177        DB = '', sm = '', pad = '', salt = this.salt+'', i = 0,
178        sl = salt.length, n = (priv.n+'').length>>1;
179 
180    if(n-hs-2 < sl){this.error_code = 6; return ""}
181    m = encoding.astr2hstr(h.hash("\x00\x00\x00\x00\x00\x00\x00\x00"+m+salt));
182    sm = "01"+encoding.astr2hstr(salt);
183    for(i = sm.length>>1; i < n-sl-hs-2; i++) pad+="00";
184    DB = this.MGF(m, n-hs-1);
185 
186    // Most significant bit - PSS could be using a byte like OAEP...
187    sm = (+('0x'+DB[(0>>>0)%DB.length])>>3==0?"00":"80") + pad + sm;
188    DB = BigInteger.toString(BigInteger.xor(BigInteger.create(DB), BigInteger.create(sm)));
189    DB += m+'bc';
190 
191    DB = this._private(DB, priv);
192    if(!!(DB.length&1)) DB='0'+DB;
193    this.error_code = 0;
194    return DB;
195   },
196 
197 /** EMSA-PKCS1-v1_5-ENCODE
198   * @private
199   */
200   _pkcs1_sig_pad: function(m, n)
201   {
202    var h = this.signature_hash, m = h.hash(m+''),
203        res = '', pad = '', i = 0;
204 
205    // DER octet string of hash
206    m = "04"+encoding.b2h(h.size)+encoding.astr2hstr(m);
207    res = h.identifier + '';
208    res = '06'+encoding.b2h(res.length>>1)+res+'0500';
209    res = '30'+encoding.b2h(res.length>>1)+res+m;
210    res = '0030'+encoding.b2h(res.length>>1)+res;
211    for(i=res.length>>1; i < n-2; i++) pad += "ff";
212    return '0001'+pad+res;
213   },
214 
215 /** RSASSA-PKCS1-V1_5-SIGN signature using rsa.signature_hash.
216   * @param {string} message ASCII string containing the data to sign
217   * @param {privateKey} priv Private Key
218   * @returns {string} Hex string representing a PKCS1v1.5 signature for the data
219   */
220   sign_pkcs1_v1_5: function(message, priv)
221   {
222    var res = '', n = (priv.n+'').length>>1;
223 
224    res = this._private(this._pkcs1_sig_pad(message, n), priv);
225    if(!!(res.length&1)) res = '0'+res;
226 
227    this.error_code = 0;
228    return res;
229   },
230 
231 /** RSASSA-PSS-VERIFY signature verification using rsa.signature_hash.
232   * @param {string} data ASCII string containing the signed data
233   * @param {string} signature Hex string containing the signature of the data
234   * @param {publicKey} pub Public key of the expected sender
235   * @returns {boolean} whether s is a valid signature for m from pub
236   */
237   verify: function(data, signature, pub)
238   {
239    var h = this.signature_hash, hs = h.size,
240        m = h.hash(data+''), s = signature+'',
241        N = BigInteger.create(pub.n+''), k = s.length>>1,
242        E = BigInteger.create(pub.e+''), n = pub.n.length>>1,
243        i = 0, DB = '', sm = '', pad = '', f = false;
244 
245    if(k != n){this.error_code = 2; return false }
246    s = BigInteger.toString(BigInteger.expMod(BigInteger.create(s), E, N));
247 
248    while(s.length != 2*n) s='0'+s;
249    if(+(s[(0>>>0)%s.length])>>3 != 0){this.error_code = 3; return false }
250 
251    for(i=0; i<s.length; i++)
252    {
253     if(i < 2*(n-hs-1)) DB += s[i];
254     else if(i < 2*(n-1)) sm += s[i];
255     else pad += s[i];
256    }
257 
258    if(pad != "bc"){ this.error_code = 7; return false }
259    s = sm; sm = this.MGF(sm, n-hs-1);
260 
261    DB = BigInteger.toString(BigInteger.xor(BigInteger.create(DB), BigInteger.create(sm)));
262    if(!!(DB.length&1)) DB='0'+DB;
263 
264    sm = "";
265    for(i=0; i < DB.length; i++)
266    {
267     pad = DB[i];
268     if(!i){ if(pad != "0" && pad != "8") return false; }
269     else if(f) sm += pad;
270     else
271     {
272      if(pad == "1" && !!(i&1)){f = true; continue;}
273      if(pad != "0"){ this.error_code = 4; return false }
274     }
275    }
276 
277    sm = encoding.hstr2astr(sm);
278    this.error_code = 0;
279    return encoding.astr2hstr(h.hash("\x00\x00\x00\x00\x00\x00\x00\x00"+m+sm)) == s;
280   },
281 
282 /** RSASSA-PKCS1-V1_5-VERIFY signature verification using rsa.signature_hash.
283   * @param {string} data ASCII string containing the signed data
284   * @param {string} signature Hex string containing the signature of the data
285   * @param {publicKey} pub Public key of the expected sender
286   * @returns {boolean} whether s is a valid signature for m from pub
287   */
288   verify_pkcs1_v1_5: function(data, signature, pub)
289   {
290    var s = signature+'', k = s.length >> 1, n = pub.n.length>>1,
291        N = BigInteger.create(pub.n+''), E = BigInteger.create(pub.e+''),
292        res = this._pkcs1_sig_pad(data, n);
293 
294    if(k != n){this.error_code = 2; return false }
295    s = BigInteger.toString(BigInteger.expMod(BigInteger.create(s), E, N));
296    while(s.length != 2*n) s='0'+s;
297    return s == res;
298   },
299 
300 /** MGF1 message generating function. Underlying hash function is rsa.mgf_hash
301   * @param {string} seed Hex string containing the seed for message generation
302   * @param {number} length Length n of the requested message in bytes
303   * @returns {string} Hex string of the desired length
304   */
305   MGF: function(seed, length)
306   {
307    var res = '', c = '', i = 0, j = 0, h = this.mgf_hash,
308        len = length<<1, hs = h.size,
309        n = (length/hs |0) + (!(length%hs) ? 0 :1);
310 
311    for(i=0; i<n; i++)
312    {
313     for(c = '', j = 0; j < 4; j++)
314      c += encoding.b2h((i>>(24-8*j))&255);
315 
316     c = encoding.astr2hstr(h.hash(encoding.hstr2astr(seed+h)));
317     for(j=0; j < c.length; j++)
318     {
319      res += c[j];
320      if(res.length == len) return res;
321     }
322    }
323    return res;
324   }
325  };
326 
327