We have new signature requirements from Central Licensing.
We're happy to comply, but,...it's a bit slow. Can you figure it out?
Service: 10.0.66.121:8008 Reference Client: 172.16.18.20/sign_faster_client-d57fe60ab04625921121656d3695beca
The library four1c2.py is the central part of the solution. The reason for foul naming of the class is because using this in any system is a horrible weakness and should never be used for any reason, especially not performance. fasterer.py and four1c2.py both use an unnecessary library gnfs1.py which I am not releasing due to code quality. It provides a list of possible primes using a sieve.
The library four1c2.py provides fuckedRSA, a class that is able to compute Chinese Remainder Theorem quickly with an arbitrary number of primes. A discussion of how CRT works is below (same as the solution from signfaster).
Say you have the primes [3, 5, 7, 11, 13, 15] as your prime factors. N is 3*5*7*11*13*15 = 225225. The decryption exponent d is computed from the encryption exponent e and phi which is a combination of the prime factors. phi = (p-1)*(q-1)*... In the example phi = 2*4*6*10*12*14 = 80640 Let's say that e = 31 d = inverse(e, phi) In this case, d would be 62431, a large number compared to N. Encryption works like this: ciphertext = pow(plaintext, e, N) Let's say our ciphertext is 110138. Then the decryption occurs like: plaintext = pow(ciphertext, d, N) In this case plaintext = 1337. In math notation: plaintext = (ciphertext ^ d) mod N This is an expensive method of decrypting (or signing which is the same operation in RSA) a piece of data. The Chinese Remainder Theorem states that you can compute the decryption with much lower exponents (and thus faster) by splitting the decryption into multiple parts and combining. Compute: q_inv = Crypto.Util.number.inverse(q, p) m_1 = pow(ct, d_P, p) m_2 = pow(ct, d_Q, q) h = (q_inv*(m_1-m_2)) % p m = m_2 + h * q
The d_P for each factor can be computed as d mod (p-1) where p is factor. The set of d_P for our example would be [1, 3, 1, 1, 7, 5]. q_inv is the inverse of q (the second prime) mod p. The first q_inv is inverse(3, 5) = 2.
The solution required a lot of iteration and I was concerned that it wouldn't solve it before the competition was over. A failed attempt to improve speed was brute force of e to get a lower d value, but that saves maybe 10% time. The major improvement over the signfaster solution was using gmpy2. gmpy2 is perhaps 50 or 100 times faster than python's pow function or the Crypto.PublicKey.RSA.sign function. If you're ever using those, you should know how slow they are.
The winning solution was this: