RSA attacks: factorisation, weiner, common modulus

hastad_attack(rsa).py

import gmpy2
import binascii
e = 3
c1 = gmpy2.mpz("")
n1 = gmpy2.mpz("")
c2 = gmpy2.mpz("")
n2 = gmpy2.mpz("")
c3 = gmpy2.mpz("")
n3 = gmpy2.mpz("")
 
M = n1*n2*n3
m1 = M/n1
m2 = M/n2
m3 = M/n3
 
t1 = c1*(m1)*gmpy2.invert(m1,n1)
t2 = c2*(m2)*gmpy2.invert(m2,n2)
t3 = c3*(m3)*gmpy2.invert(m3,n3)
 
x = (t1+t2+t3) % M # chinese reminder theorem
m, exact = gmpy2.iroot(x,e) # recover m
if exact:
    print binascii.unhexlify(gmpy2.digits(m,16)) # convert int -> hex -> ascii
 #blog: hastad-attack PicoCtf-crypto

rsa_common_modulus.py

import sys

#Modulus N
#N=402394248802762560784459411647796431108620322919897426002417858465984510150839043308712123310510922610690378085519407742502585978563438101321191019034005392771936629869360205383247721026151449660543966528254014636648532640397857580791648563954248342700568953634713286153354659774351731627683020456167612375777

#Public key exponent for first user
#e1=3

#Public key exponent for second user 0x10001
#e2=65537

#First Ciphertext 
#c1=239450055536579126410433057119955568243208878037441558052345538060429910227864196906345427754000499641521575512944473380047865623679664401229365345208068050995600248796358129950676950842724758743044543343426938845678892776396315240898265648919893384723100132425351735921836372375270138768751862889295179915967

#Second Ciphertext
#c2=138372640918712441635048432796183745163164033759933692015738688043514876808030419408866658926149572619049975479533518038543123781439635367988204599740411304464710538234675409552954543439980522243416932759834006973717964032712098473752496471182275216438174279723470286674311474283278293265668947915374771552561


def xgcd(a,b):
	if b == 0:
	 return [1,0,a]
	else:
	 x,y,d = xgcd(b, a%b)
	 return [y, x - (a//b)*y, d]


def gcd(a, b):
    # Return the GCD of a and b using Euclid's Algorithm
    while a != 0:
        a, b = b % a, a
    return b

#c2 would be a and Modulus N would be m
def modInverse(a, m):

    if gcd(a, m) != 1:
        return None # no mod inverse if a & m aren't relatively prime

    u1, u2, u3 = 1, 0, a
    v1, v2, v3 = 0, 1, m
    while v3 != 0:
        q = u3 // v3 # // is the integer division operator
        v1, v2, v3, u1, u2, u3 = (u1 - q * v1), (u2 - q * v2), (u3 - q * v3), v1, v2, v3
    return u1 % m




def main():
	if len(sys.argv) < 6:
		print("Insufficient parameters, Please provide parameters in order of N,e1,e2,c1,c2")
		return
	
        N=long(sys.argv[1])
	e1=long(sys.argv[2])
	e2=long(sys.argv[3])
	c1=long(sys.argv[4])
	c2=long(sys.argv[5])
	
	euclidConstants=xgcd(e1,e2)
	a=euclidConstants[0]	
	b=euclidConstants[1]

	eq1=modInverse(c2,N)


	#(c1^a * eq1^-b) mod N
	result1=pow(eq1,-b,N)
	result2=pow(c1,a,N)

	result3=result1*result2
	finalresult=result3%N
	#print finalresult

	hexresult=hex(finalresult)[2:-1]
	#print hexresult

	hextoascii=str(hexresult).decode("hex")
	print hextoascii


if __name__ == "__main__":
    	main()

# from github/vaibhav-agarwal

rsacrack.py

#!/usr/bin/python
from sys import*;from string import*;a=argv;[s,p,q]=filter(lambda x:x[:1]!=
'-',a);d='-d'in a;e,n=atol(p,16),atol(q,16);l=(len(q)+1)/2;o,inb=l-d,l-1+d
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))) 
  # for cipher text decryption (cat secret | ) from github-ganapati/rsactftool

rsatool.py

#!/usr/bin/env python2
import base64, fractions, optparse, random
try:
    import gmpy
except ImportError as e:
    try:
        import gmpy2 as gmpy
    except ImportError:
        raise e

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

        if self.p != self.q:
            phi = (self.p - 1) * (self.q - 1)
        else:
            phi = (self.p ** 2) - self.p

        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()).decode()).encode()

    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 range(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 filename')
    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 as e:
        parser.print_help()
        parser.error(e.msg)
     # from github/blog/site

weiner_attack(d).py

# The big Wiener attack  
# Claude Jaspart - June 14th, 2016
#
# elmacfish 
#
# python wiener.py
#
# Enjoy !

import math
from fractions import gcd
import gmpy2


#checking if d is odd
def verif_odd_den(den) :
        if den%2 == 1:
                return True
        else:
                return False



#checking if the roots are whole numbers
def verif_quadra(phi, N) :
        # coefficients are initialized
        a=1
        b=phi - N - 1
        c=N

        #calculation of the determinant
        delta = b*b-4*a*c
        if delta < 0 :
                return  False

        #processing the roots
        n=gmpy2.mpz(delta)
        gmpy2.get_context().precision=2048
        det=gmpy2.sqrt(n)

        num1 = (-b + det)
        num2 = (-b - det)
        den  = 2*a
       
        k1 = int(num1/den)
        r1 = num1 - k1 * den
       
        k2 = int(num2/den)
        r2 = num2 - k2 * den       

        if  r1 == 0.0 and r2 == 0.0 :
                return True
        else:
                return False


#calculates the phi(N)
def calc_phi(e,k,d) :
        num = ( e * d - 1)
        den = k
       
        r = int(num/den)
       
        if num - r * den == 0:
                return num/den
        else :
                return 0



# Program starts here
# -------------------


e=4545  #(decimal)
N=6790 #(decimal)




# continued fraction coefficient processing part
eprime = e
nprime = N
coeff = []
profondeur = 0        # defines how many coefficients there are

coeff.append(0)
while (eprime >= 1):
        profondeur = profondeur + 1
        k = int(nprime/eprime)
        r = nprime - k * eprime        
        coeff.append(k)
        nprime = eprime
        eprime = r
       

       
# prints the continued fractions coefficients
'''
for i in coeff:
        print i,
               
print ''
'''

# calcul du (num/den) de la fraction pour chaque profondeur
found = False                #for the end message
for n in range (1,profondeur) :
       
        # counter init
        cptr = n

        # starting values
        num = coeff[cptr]        # start from right to left in the coeff array
        den = 1

        while ( cptr > 0 ) :

                # swap denominator and numerator
                tmpnum = num       
                num = den
                den = tmpnum

                # processing the new value of the numerator,
                # denominator doesnt change
                num = coeff[cptr-1] * den + num

                # preparing to retrieve previous coefficient
                cptr = cptr - 1

        # some debug prints
        #print 'k/d = ' , num, '/', den

        #calculates phi
        phi = calc_phi(e,num,den)

        # tests all 3 criteria and exits at first valid value
        if ( (phi > 0) and verif_odd_den(den) and verif_quadra(phi, N)):
                print "A valid d was found : "
                print den
                found = True
                break

# end message
if not found:
        print "No valid d found !"
       

For more simple and direct usage see: RsaCtfTools