{naive_is_prime,random_prime} = require './primegen' bn = require './bn' {nbits,nbv,nbi,BigInteger} = bn {bufeq_secure,ASP} = require './util' {make_esc} = require 'iced-error' konst = require './const' C = konst.openpgp K = konst.kb {SHA512} = require './hash' {eme_pkcs1_encode,eme_pkcs1_decode,emsa_pkcs1_decode,emsa_pkcs1_encode} = require './pad' {SRF,MRF} = require './rand' {BaseKey,BaseKeyPair} = require './basekeypair' #======================================================================= class Priv extends BaseKey constructor : ({@p,@q,@d,@dmp1,@dmq1,@u,@pub}) -> #-------------------- decrypt : (c,cb) -> await @mod_pow_d_crt c, defer x cb null, x #-------------------- sign : (m,cb) -> @mod_pow_d_crt m, cb #-------------------- @ORDER : [ 'd', 'p', 'q', 'u' ] ORDER : Priv.ORDER #-------------------- n : () -> @p.multiply(@q) phi : () -> @p.subtract(BigInteger.ONE).multiply(@q.subtract(BigInteger.ONE)) lambda : () -> @phi.divide(@p.subtract(BigInteger.ONE).gcd(@q.subtract(BigInteger.ONE))) #-------------------- @alloc : (raw, pub) -> BaseKey.alloc Priv, raw, { pub } #-------------------- # Use Chinese remainder theorem to compute (x^d mod n) quickly. mod_pow_d_crt : (x,cb) -> # pre-compute dP, dQ @dP = @d.mod(@p.subtract(BigInteger.ONE)) unless @dP? @dQ = @d.mod(@q.subtract(BigInteger.ONE)) unless @dQ? # pre-compute qInv if necessary @qInv = @q.modInverse(@p) unless @qInv? ### Chinese remainder theorem (CRT) states: Suppose n1, n2, ..., nk are positive integers which are pairwise coprime (n1 and n2 have no common factors other than 1). For any integers x1, x2, ..., xk there exists an integer x solving the system of simultaneous congruences (where ~= means modularly congruent so a ~= b mod n means a mod n = b mod n): x ~= x1 mod n1 x ~= x2 mod n2 ... x ~= xk mod nk This system of congruences has a single simultaneous solution x between 0 and n - 1. Furthermore, each xk solution and x itself is congruent modulo the product n = n1*n2*...*nk. So x1 mod n = x2 mod n = xk mod n = x mod n. The single simultaneous solution x can be solved with the following equation: x = sum(xi*ri*si) mod n where ri = n/ni and si = ri^-1 mod ni. Where x is less than n, xi = x mod ni. For RSA we are only concerned with k = 2. The modulus n = pq, where p and q are coprime. The RSA decryption algorithm is: y = x^d mod n Given the above: x1 = x^d mod p r1 = n/p = q s1 = q^-1 mod p x2 = x^d mod q r2 = n/q = p s2 = p^-1 mod q So y = (x1r1s1 + x2r2s2) mod n = ((x^d mod p)q(q^-1 mod p) + (x^d mod q)p(p^-1 mod q)) mod n According to Fermat's Little Theorem, if the modulus P is prime, for any integer A not evenly divisible by P, A^(P-1) ~= 1 mod P. Since A is not divisible by P it follows that if: N ~= M mod (P - 1), then A^N mod P = A^M mod P. Therefore: A^N mod P = A^(M mod (P - 1)) mod P. (The latter takes less effort to calculate). In order to calculate x^d mod p more quickly the exponent d mod (p - 1) is stored in the RSA private key (the same is done for x^d mod q). These values are referred to as dP and dQ respectively. Therefore we now have: y = ((x^dP mod p)q(q^-1 mod p) + (x^dQ mod q)p(p^-1 mod q)) mod n Since we'll be reducing x^dP by modulo p (same for q) we can also reduce x by p (and q respectively) before hand. Therefore, let xp = ((x mod p)^dP mod p), and xq = ((x mod q)^dQ mod q), yielding: y = (xp*q*(q^-1 mod p) + xq*p*(p^-1 mod q)) mod n This can be further reduced to a simple algorithm that only requires 1 inverse (the q inverse is used) to be used and stored. The algorithm is called Garner's algorithm. If qInv is the inverse of q, we simply calculate: y = (qInv*(xp - xq) mod p) * q + xq However, there are two further complications. First, we need to ensure that xp > xq to prevent signed BigIntegers from being used so we add p until this is true (since we will be mod'ing with p anyway). Then, there is a known timing attack on algorithms using the CRT. To mitigate this risk, "cryptographic blinding" should be used (*Not yet implemented*). This requires simply generating a random number r between 0 and n-1 and its inverse and multiplying x by r^e before calculating y and then multiplying y by r^-1 afterwards. ### # Cryptographic blinding: compute random r, # r_e <- r^e mod n # and x <- x*r_e mod n n = @pub.n await SRF().random_zn n, defer r r_inv = r.modInverse(n) r_e = r.modPow(@pub.e,n) x_1 = x.multiply(r_e).mod(n) # calculate xp and xq xp = x_1.mod(@p).modPow(@dP, @p) xq = x_1.mod(@q).modPow(@dQ, @q) # xp must be larger than xq to avoid signed bit usage while xp.compareTo(xq) < 0 xp = xp.add @p # do last step y_0 = xp.subtract(xq).multiply(@qInv).mod(@p).multiply(@q).add(xq) # multiply by r^-1... y = y_0.multiply(r_inv).mod(n) cb y #======================================================================= class Pub extends BaseKey #---------------- @type : C.public_key_algorithms.RSA type : Pub.type #---------------- @ORDER : [ 'n', 'e' ] ORDER : Pub.ORDER #---------------- constructor : ({@n,@e}) -> encrypt : (p, cb) -> @mod_pow p, @e, cb verify : (s, cb) -> @mod_pow s, @e, cb nbits : () -> @n?.bitLength() #---------------- @alloc : (raw) -> BaseKey.alloc Pub, raw #---------------- mod_pow : (x,d,cb) -> cb x.modPow(d,@n) #---------------- validity_check : (cb) -> err = if (not @n.gcd(@e).equals(BigInteger.ONE)) then new Error "gcd(n,e) != 1" else if (not @n.mod(nbv(2)).equals(BigInteger.ONE)) then new Error "n % 2 != 1" else if (@e.compareTo(BigInteger.ONE) <= 0) then new Error "e <= 1" else if (@e.bitLength() > 32) then new Error "e=#{@e} > 2^32" # As of Issue #47, we've disabled this check #else if not naive_is_prime(@e.intValue()) then new Error "e #{@e} isn't prime!" else null cb err #======================================================================= class Pair extends BaseKeyPair @type : C.public_key_algorithms.RSA type : Pair.type get_type : () -> @type @klass_name : 'RSA' #---------------- @Pub : Pub Pub : Pub @Priv : Priv Priv : Priv #---------------- constructor : ({priv, pub}) -> super { priv, pub } #---------------- @parse : (pub_raw) -> BaseKeyPair.parse Pair, pub_raw @alloc : ({pub, priv}) -> BaseKeyPair.alloc { pub, priv } #---------------- # All subkeys use the same parent algorithm as the parent -- RSA @subkey_algo : (flags) -> Pair #---------------- sanity_check : (cb) -> err = if @priv.n().compareTo(@pub.n) is 0 then null else new Error "pq != n" unless err? x0 = MRF().random_zn @pub.n await @encrypt x0, defer x1 await @decrypt x1, defer err, x2 if not err? and x0.compareTo(x2) isnt 0 err = new Error "Decrypt/encrypt failed" unless err? y0 = MRF().random_zn @pub.n await @sign y0, defer y1 await @verify y1, defer y2 err = new Error "Sign/verify failed" unless y0.compareTo(y2) is 0 cb err #---------------- # Parse a signature out of a packet # # @param {SlicerBuffer} slice The input slice # @return {BigInteger} the Signature # @throw {Error} an Error if there was an overrun of the packet. @parse_sig : (slice) -> [err, ret, raw, n] = bn.mpi_from_buffer slice.peek_rest_to_buffer() throw err if err? slice.advance(n) ret #---------------- encrypt : (p, cb) -> @pub.encrypt p, cb decrypt : (c, cb) -> @priv.decrypt c, cb max_value : () -> @pub.n #---------------- @make : ( { p, q, e, phi, p1, q1, lambda } ) -> n = p.multiply(q) d = e.modInverse lambda dmp1 = d.mod p1 dmq1 = d.mod q1 u = p.modInverse q pub = new Pub { n, e } priv = new Priv { p, q, d, dmp1, dmq1, u, pub } new Pair { priv, pub } #---------------- to_openpgp : () -> key = new (new RSA).keyObject() key.n = @pub.n key.e = @pub.e.intValue() key.ee = @pub.e key.d = @priv.d key.p = @priv.p key.q = @priv.q key.dmp1 = @priv.dmp1 key.dmq1 = @priv.dmq1 key.u = @priv.u key #---------------- sign : (m, cb) -> @priv.sign m, cb verify : (s, cb) -> @pub.verify s, cb #---------------- pad_and_encrypt : (data, params, cb) -> err = ret = null await eme_pkcs1_encode data, @pub.n.mpi_byte_length(), defer err, m unless err? await @encrypt m, defer ct ret = @export_output { y_mpi : ct } cb err, ret #---------------- # @param {Output} ciphertext A ciphertext in RSA::Output form # decrypt_and_unpad : (ciphertext, params, cb) -> err = ret = null await @decrypt ciphertext.y(), defer err, p unless err? b = p.to_padded_octets @pub.n [err, ret] = eme_pkcs1_decode b cb err, ret #---------------- pad_and_sign : (data, {hasher}, cb) -> hasher or= SHA512 hashed_data = hasher data m = emsa_pkcs1_encode hashed_data, @pub.n.mpi_byte_length(), {hasher} await @sign m, defer sig cb null, sig.to_mpi_buffer() #---------------- verify_unpad_and_check_hash : ({sig, data, hasher, hash}, cb) -> err = null [err, sig] = bn.mpi_from_buffer sig if Buffer.isBuffer sig unless err? await @verify sig, defer v b = v.to_padded_octets @pub.n [err, hd1] = emsa_pkcs1_decode b, hasher unless err? hash or= hasher data err = new Error "hash mismatch" unless bufeq_secure hd1, hash cb err #---------------- @generate : ({nbits, iters, e, asp}, cb) -> e or= ((1 << 16) + 1) e_orig = e nbits or= 4096 iters or= 10 asp or= new ASP({}) e = nbv e_orig esc = make_esc cb, "generate_rsa_keypair" go = true nbits >>= 1 # since we have 2 primes... while go await random_prime { asp : asp.section('p'), e, nbits, iters }, esc defer p await asp.progress { what : "found" , p }, esc defer() await random_prime { asp : asp.section('q'), e, nbits, iters }, esc defer q await asp.progress { what : "found" , q }, esc defer() [p,q] = [q,p] if p.compareTo(q) <= 0 q1 = q.subtract BigInteger.ONE p1 = p.subtract BigInteger.ONE phi = p1.multiply q1 lambda = phi.divide(q1.gcd(p1)) if phi.gcd(e).compareTo(BigInteger.ONE) isnt 0 progress_hook? { what : "unlucky_phi" } go = true else go = false key = Pair.make { p, q, e, phi, p1, q1, lambda } cb null, key #---------------- @parse_output : (buf) -> (Output.parse buf) export_output : (args) -> new Output args #---------------- validity_check : (cb) -> await @pub.validity_check defer err cb err #======================================================================= class Output constructor : ({@y_mpi, @y_buf}) -> #------------------- @parse : (buf) -> [err, ret, raw, n] = bn.mpi_from_buffer buf throw err if err? throw new Error "junk at the end of input" unless raw.length is 0 new Output { y_mpi : ret } #------------------- y : () -> @y_mpi #------------------- hide : ({key, max, slosh}, cb) -> max or= 8192 slosh or= 128 await key.hide { i : @y(), max, slosh }, defer err, i unless err? @y_mpi = i @y_buf = null cb err #------------------- find : ({key}) -> @y_mpi = key.find @y_mpi #------------------- output : () -> (@y_buf or @y_mpi.to_mpi_buffer()) #======================================================================= exports.RSA = exports.Pair = Pair exports.Output = Output #=======================================================================