# CSCamp CTF Quals 2k13: Crypto - public is enough! (400 points)

# grep -v - public.pem | tr -d '\n' | base64 -d | openssl asn1parse -inform DER -i
    0:d=0  hl=2 l= 124 cons: SEQUENCE
    2:d=1  hl=2 l=  13 cons:  SEQUENCE
    4:d=2  hl=2 l=   9 prim:   OBJECT            :rsaEncryption
   15:d=2  hl=2 l=   0 prim:   NULL
   17:d=1  hl=2 l= 107 prim:  BIT STRING
# grep -v - public.pem | tr -d '\n' | base64 -d | openssl asn1parse -inform DER -i -strparse 17
    0:d=0  hl=2 l= 104 cons: SEQUENCE
    2:d=1  hl=2 l=  97 prim:  INTEGER           :CAD984557C97E039431A226AD727F0C6D43EF3D418469F1B375049B229843EE9F83B1F97738AC274F5F61F401F21F1913E4B64BB31B55A38D398C0DFED00B1392F0889711C44B359E7976C617FCC734F06E3E95C26476091B52F462E79413DB5
  101:d=1  hl=2 l=   3 prim:  INTEGER           :010001
# openssl rsa -pubin -inform PEM -text -noout < public.pem
Public-Key: (768 bit)
Modulus:
    00:ca:d9:84:55:7c:97:e0:39:43:1a:22:6a:d7:27:
    f0:c6:d4:3e:f3:d4:18:46:9f:1b:37:50:49:b2:29:
    84:3e:e9:f8:3b:1f:97:73:8a:c2:74:f5:f6:1f:40:
    1f:21:f1:91:3e:4b:64:bb:31:b5:5a:38:d3:98:c0:
    df:ed:00:b1:39:2f:08:89:71:1c:44:b3:59:e7:97:
    6c:61:7f:cc:73:4f:06:e3:e9:5c:26:47:60:91:b5:
    2f:46:2e:79:41:3d:b5
Exponent: 65537 (0x10001)
# # Find p and q using this URL http://www.factordb.com/index.php
n = 1230186684530117755130494958384962720772853569595334792197322452151726400507263657518745202199786469389956474942774063845925192557326303453731548268507917026122142913461670429214311602221240479274737794080665351419597459856902143413
p = 33478071698956898786044169848212690817704794983713768568912431388982883793878002287614711652531743087737814467999489
q = 36746043666799590428244633799627952632279158164343087642676032283815739666511279233373417143396810270092798736308917

# ipython
: import gmpy
: p = 33478071698956898786044169848212690817704794983713768568912431388982883793878002287614711652531743087737814467999489
: q = 36746043666799590428244633799627952632279158164343087642676032283815739666511279233373417143396810270092798736308917
: totien = (p-1) * (q-1)
: e = 65537
: d = hex(gmpy.invert(e,totien))
: d
'0x740de48760442835baad5e1990453a9d16db7976d3f8bb98bf99c0c01cbe9b9c12b808c80683d1e346c16c79ac162874f28ca610c1b97e5e1ffae95725ce0c6b031c3e188b17187a793b322cc4004c568e76c9b258542ea2a2d6ecd462fff401'

# cat rsatool.py
#!/usr/bin/python2
import base64, fractions, optparse, random
import gmpy

from pyasn1.codec.der import encoder
from pyasn1.type.univ import *

PEM_TEMPLATE = '-----BEGIN RSA PRIVATE KEY-----\n%s-----END RSA PRIVATE KEY-----\n'
DEFAULT_EXP = 65537

def factor_modulus(n, d, e):
    """
    Efficiently recover non-trivial factors of n

    See: Handbook of Applied Cryptography
    8.2.2 Security of RSA -> (i) Relation to factoring (p.287)

    http://www.cacr.math.uwaterloo.ca/hac/
    """
    t = (e * d - 1)
    s = 0

    while True:
        quotient, remainder = divmod(t, 2)

        if remainder != 0:
            break

        s += 1
        t = quotient

    found = False

    while not found:
        i = 1
        a = random.randint(1,n-1)

        while i <= s and not found:
            c1 = pow(a, pow(2, i-1, n) * t, n)
            c2 = pow(a, pow(2, i, n) * t, n)

            found = c1 != 1 and c1 != (-1 % n) and c2 == 1

            i += 1

    p = fractions.gcd(c1-1, n)
    q = (n / p)

    return p, q

class RSA:
    def __init__(self, p=None, q=None, n=None, d=None, e=DEFAULT_EXP):
        """
        Initialize RSA instance using primes (p, q)
        or modulus and private exponent (n, d)
        """

        self.e = e

        if p and q:
            assert gmpy.is_prime(p), 'p is not prime'
            assert gmpy.is_prime(q), 'q is not prime'

            self.p = p
            self.q = q
        elif n and d:   
            self.p, self.q = factor_modulus(n, d, e)
        else:
            raise ArgumentError('Either (p, q) or (n, d) must be provided')

        self._calc_values()

    def _calc_values(self):
        self.n = self.p * self.q

        phi = (self.p - 1) * (self.q - 1)
        self.d = gmpy.invert(self.e, phi)

        # CRT-RSA precomputation
        self.dP = self.d % (self.p - 1)
        self.dQ = self.d % (self.q - 1)
        self.qInv = gmpy.invert(self.q, self.p)

    def to_pem(self):
        """
        Return OpenSSL-compatible PEM encoded key
        """
        return PEM_TEMPLATE % base64.encodestring(self.to_der())

    def to_der(self):
        """
        Return parameters as OpenSSL compatible DER encoded key
        """
        seq = Sequence()

        for x in [0, self.n, self.e, self.d, self.p, self.q, self.dP, self.dQ, self.qInv]:
            seq.setComponentByPosition(len(seq), Integer(x))

        return encoder.encode(seq)

    def dump(self, verbose):
        vars = ['n', 'e', 'd', 'p', 'q']

        if verbose:
            vars += ['dP', 'dQ', 'qInv']

        for v in vars:
            self._dumpvar(v)

    def _dumpvar(self, var):
        val = getattr(self, var)

        parts = lambda s, l: '\n'.join([s[i:i+l] for i in xrange(0, len(s), l)])

        if len(str(val)) <= 40:
            print '%s = %d (%#x)\n' % (var, val, val)
        else:
            print '%s =' % var
            print parts('%x' % val, 80) + '\n'


if __name__ == '__main__':
    parser = optparse.OptionParser()

    parser.add_option('-p', dest='p', help='prime', type='int')
    parser.add_option('-q', dest='q', help='prime', type='int')
    parser.add_option('-n', dest='n', help='modulus', type='int')
    parser.add_option('-d', dest='d', help='private exponent', type='int')
    parser.add_option('-e', dest='e', help='public exponent (default: %d)' % DEFAULT_EXP, type='int', default=DEFAULT_EXP)
    parser.add_option('-o', dest='filename', help='output filname')
    parser.add_option('-f', dest='format', help='output format (DER, PEM) (default: PEM)', type='choice', choices=['DER', 'PEM'], default='PEM')
    parser.add_option('-v', dest='verbose', help='also display CRT-RSA representation', action='store_true', default=False)

    try:
        (options, args) = parser.parse_args()

        if options.p and options.q:
            print 'Using (p, q) to initialise RSA instance\n'
            rsa = RSA(p=options.p, q=options.q, e=options.e)
        elif options.n and options.d:
            print 'Using (n, d) to initialise RSA instance\n'
            rsa = RSA(n=options.n, d=options.d, e=options.e)
        else:
            parser.print_help()
            parser.error('Either (p, q) or (n, d) needs to be specified')

        rsa.dump(options.verbose)

        if options.filename:
            print 'Saving %s as %s' % (options.format, options.filename)


            if options.format == 'PEM':
                data = rsa.to_pem()
            elif options.format == 'DER':
                data = rsa.to_der()

            fp = open(options.filename, 'wb')
            fp.write(data)
            fp.close()

    except optparse.OptionValueError, e:
        parser.print_help()
        parser.error(e.msg)
# ./rsatool.py -p 33478071698956898786044169848212690817704794983713768568912431388982883793878002287614711652531743087737814467999489 -q 36746043666799590428244633799627952632279158164343087642676032283815739666511279233373417143396810270092798736308917 -n 1230186684530117755130494958384962720772853569595334792197322452151726400507263657518745202199786469389956474942774063845925192557326303453731548268507917026122142913461670429214311602221240479274737794080665351419597459856902143413 -e 65537
Using (p, q) to initialise RSA instance

n =
cad984557c97e039431a226ad727f0c6d43ef3d418469f1b375049b229843ee9f83b1f97738ac274
f5f61f401f21f1913e4b64bb31b55a38d398c0dfed00b1392f0889711c44b359e7976c617fcc734f
06e3e95c26476091b52f462e79413db5

e = 65537 (0x10001)

d =
740de48760442835baad5e1990453a9d16db7976d3f8bb98bf99c0c01cbe9b9c12b808c80683d1e3
46c16c79ac162874f28ca610c1b97e5e1ffae95725ce0c6b031c3e188b17187a793b322cc4004c56
8e76c9b258542ea2a2d6ecd462fff401

p =
d982ec7b440e2869d2535e51f91bacc3eb6eba042e106e6f875c3d17e53db65fffd6e4e9a36084ce
60f83d754dd7f701

q =
eebe6dd23ce7e99c0e2249fecc4418c34af74e418bfa714c3791828414ab18f32fd7e093062a49b0
30225cc845f99ab5

# ipython
: from Crypto.PublicKey import RSA
: keypair = RSA.generate(1024)
: keypair.n = 1230186684530117755130494958384962720772853569595334792197322452151726400507263657518745202199786469389956474942774063845925192557326303453731548268507917026122142913461670429214311602221240479274737794080665351419597459856902143413
: keypair.e = 65537
: keypair.d = 703813872109751212728960868893055483396831478279095442779477323396386489876250832944220079595968592852532432488202250497425262918616760886811596907743384527001944888359578241816763079495533278518938372814827410628647251148091159553
: keypair.p = 33478071698956898786044169848212690817704794983713768568912431388982883793878002287614711652531743087737814467999489
: keypair.q = 36746043666799590428244633799627952632279158164343087642676032283815739666511279233373417143396810270092798736308917
: private = open('private.pem','w')
: private.write(keypair.exportKey())
: private.close()
: exit
# openssl rsautl -decrypt -in message.enc -out /dev/tty -inkey private.pem
F4ct0r!zaTi0N

# cat RSAcrack.py
#!/usr/bin/python

from sys import*
from string import*

a = argv
[s,p,q] = filter(lambda x:x[:1]!= '-',a)
print "s = " + str(s)
print "p = " + str(p)
print "q = " + str(q)
d='-d' in a
print "d = " + str(d)
e, n = atol(p,16), atol(q,16)
print "e = " + str(e)
print "n = " + str(n)
l = (len(q) + 1) / 2
print "l = " + str(l)
o, inb = l-d, l-1+d
print "o = " + str(o)
print "inb = " + str(inb)
while s:
 s = stdin.read(inb)
 s and map(stdout.write, map(lambda i, b=pow(reduce(lambda x,y : (x<<8L)+y, map(ord,s)), e, n) : chr(b>>8*i&255), range(o-1, -1, -1)))
# cat message.enc | ./RSAcrack.py -d 740de48760442835baad5e1990453a9d16db7976d3f8bb98bf99c0c01cbe9b9c12b808c80683d1e346c16c79ac162874f28ca610c1b97e5e1ffae95725ce0c6b031c3e188b17187a793b322cc4004c568e76c9b258542ea2a2d6ecd462fff401 cad984557c97e039431a226ad727f0c6d43ef3d418469f1b375049b229843ee9f83b1f97738ac274f5f61f401f21f1913e4b64bb31b55a38d398c0dfed00b1392f0889711c44b359e7976c617fcc734f06e3e95c26476091b52f462e79413db5 | strings
F4ct0r!zaTi0N