Infinite Descent

#!/usr/bin/env python
#**********************************************************************
# filename: fasterprimes.py
# version: 0.06.2-alpha
# release date: 20170806
# dev: Cayce Pollard
# qa: NOT PASSED, open defects.
# finds a specified length prime, then a neighbouring prime for speed. 
# DEFECTS
# ID[243], category A4, owner: CayceP, comment: may have to be run several times to generate valid RSA values  
# ID[552], category A9, owner: AppSec, comment: Do neighbouring primes present a security risk?
#**********************************************************************


from Crypto.Util import number
from Crypto.PublicKey.RSA import construct
from Crypto.PublicKey import RSA
import sympy


def egcd(a, b):
    if a == 0:
        return (b, 0, 1)
    else:
        g, x, y = egcd(b % a, a)
        return (g, y - (b // a) * x, x)


def getPQ():
    n_length =512 #generates a 1024 bit key.
    while True:
        firstprime = number.getPrime(n_length) #let's get our first number
    lowerp = firstprime - 10
    upperp = firstprime + 10       
    for x in range(lowerp,upperp): #getPrime takes too long so we'll find a nearby prime for q
           if x == firstprime:
             continue
           else:   
             if sympy.isprime(x):
                secondprime = x
                return firstprime, secondprime
                break
        return 1, 1
     
e = 65537

while True:
    p, q = getPQ()  
    if p == 1:
        print("still trying")
    else:
      break


n = p*q #we make our modulus
phi = (p-1)*(q-1) #this one is for making the private key
gcd, d, b = egcd(e, phi) #now we have all our RSA values. 

key_params = (long(n), long(e), long(d))
key = RSA.construct(key_params)
print key.exportKey()
print key.publickey().exportKey()
#keep the pre-shared key below 100 bytes. 
message = #put the message here.
#message = [ord(c) for c in message] #comment out if message is int.
#message = int(''.join(map(str,message)))
print ('message: ', message)
RSAsecret = key.encrypt(int(message),'') #check the encryption works 
print ('RSAsecret: ', RSAsecret) #send this to the recipient
print ('message: ', message) #don't send this you idiot.
print ('Secret check:', key.decrypt(RSAsecret)) #check the message matches the decrypted message/

#!/usr/bin/env python
#**********************************************************************
# filename: AESbootstrap.py
# version: 0.11.7-alpha
# release date: 20170801
# dev: Cayce Pollard
# qa: Jonathan Norrell
# instantiate mersenne each time, feed it every 3 digits of the shared secret
# to establish a shared AES128 key.
#
#**********************************************************************

#textbook mersenne twister from https://en.wikipedia.org/wiki/Mersenne_Twister#Python_implementation (no rolling your own!)  

class mersenne(object):

    def __init__(self, seed):
        # Initialize the index to 0
        self.index = 624
        self.mt = [0] * 624
        self.mt[0] = seed  # Initialize the initial state to the seed
        for i in range(1, 624):
            initval = int(0xFFFFFFFF & (1812433253 * (self.mt[i - 1] ^ self.mt[i - 1] >> 30) + i))
            # print(initval)
            self.mt[i] = initval


    def extract_number(self):
        if self.index >= 624:
            self.twist()

        y = self.mt[self.index]

        # Right shift by 11 bits
        y = y ^ y >> 11
        # Shift y left by 7 and take the bitwise and of 2636928640
        y = y ^ y << 7 & 2636928640
        # Shift y left by 15 and take the bitwise and of y and 4022730752
        y = y ^ y << 15 & 4022730752
        # Right shift by 18 bits
        y = y ^ y >> 18

        self.index = self.index + 1

        return int(0xFFFFFFFF & y)

    def twist(self):
        for i in range(624):
            # Get the most significant bit and add it to the less significant
            # bits of the next number
            y = int(0xFFFFFFFF & ((self.mt[i] & 0x80000000) + (self.mt[(i + 1) % 624] & 0x7fffffff)))
            self.mt[i] = self.mt[(i + 397) % 624] ^ y >> 1

            if y % 2 != 0:
                self.mt[i] = self.mt[i] ^ 0x9908b0df
        self.index = 0
        #test


#******************************************************************************
#test tool:
#use this to convert a triplet from the decoded value as seedval
#do this across each of the values to check the candidate against the AESkey.
#******************************************************************************
def gen_and_check(genseed):
    # make an object
    x = mersenne(genseed)
    y = (x.extract_number() & 0xFF) #only interested in LSBs. Use the mask as we don't care about the rest

    return y #candidate for comparison.

list = str(bin(gen_and_check(seedval)))
candidate = list[2::]
candidate = candidate.zfill(8)

From:	CayceP <cayce.pollard@>
Sent:	11 August 2017 18:15
To:	Deschain, Roland
Subject:	Progress update

Hi Rolly,

Just a quick update. We've addressed your issues with the numpy PSNG by ditching it and created a mersenne twister from scratch.
This will be used as the pre-secret from the RSA exchange for bootstrapping the AES comms.

We have some problems with the RSA generator that we're ironing out. Security have some questions around the
way primes are chosen but I think they're just getting in the way. To prove it's working just fine I've sent your
private key through secure comms and your public key is below with the message; we've also used this to encrypt a pre-shared
secret. Can you decrypt with your private key and check the pre-shared key works with the twister?

Have a good weekend,

CayceP


-----BEGIN PUBLIC KEY-----
MIGeMA0GCSqGSIb3DQEBAQUAA4GMADCBiAKBgFbDk+zYy1tbjwPpsTWbYjIfBtZk
walARbJxLg6QhyalsGnBx064VFIH9XIKzPK/Dt1RzMO68gy7zLOiyipPtYb2n0M6
WcdDGgw9J9+xx4HjXZCHx4h4zQhfQeOYymeSPewXJOe+GT31ymz6/Q1Ulyq/jWnD
XZogxfbXi6bIwuN7AgMBAAE=
-----END PUBLIC KEY-----


-----BEGIN MESSAGE-----
41296290787170212566581926747559000694979534392034439796933335542554551981322424774631715454669002723657175134418412556653226439790475349107756702973735895193117931356004359775501074138668004417061809481535231402802835349794859992556874148430578703014721700812262863679987426564893631600671862958451813895661  
-----END MESSAGE-----

def getPQ():
    n_length =512 #generates a 1024 bit key.
    while True:
        firstprime = number.getPrime(n_length) #let's get our first number
    lowerp = firstprime - 10
    upperp = firstprime + 10       
    for x in range(lowerp,upperp): #getPrime takes too long so we'll find a nearby prime for q  
           if x == firstprime:
             continue
           else:   
             if sympy.isprime(x):
                secondprime = x
                return firstprime, secondprime
                break
        return 1, 1
     
e = 65537

while True:
    p, q = getPQ()  
    if p == 1:
        print("still trying")
    else:
      break


n = p*q #we make our modulus

$ python3 -q
>>> from Crypto.PublicKey import RSA
>>> from Crypto.Util.number import isPrime
>>> from gmpy2 import iroot
>>> key = RSA.import_key('''-----BEGIN PUBLIC KEY-----
... MIGeMA0GCSqGSIb3DQEBAQUAA4GMADCBiAKBgFbDk+zYy1tbjwPpsTWbYjIfBtZk
... walARbJxLg6QhyalsGnBx064VFIH9XIKzPK/Dt1RzMO68gy7zLOiyipPtYb2n0M6
... WcdDGgw9J9+xx4HjXZCHx4h4zQhfQeOYymeSPewXJOe+GT31ymz6/Q1Ulyq/jWnD
... XZogxfbXi6bIwuN7AgMBAAE=
... -----END PUBLIC KEY-----
... ''')
>>> key.e
65537
>>> key.n
60927735877056559130803069919621859729817223816091468870468728150535102345085544195001142179497747300756976118359991531766104121379004146329976732080428122272205922112100073487631152244297343150154109815442681320311122134731991282281969152492933055882377304091844616671159896354284349735375653609635116671867  
>>> p = iroot(key.n, 2)[0]
>>> while not isPrime(p):
...     p += 1
...
>>> q = p - 1
>>> while not isPrime(q):
...     q -= 1
...
>>> assert key.n == p * q

>>> c = 41296290787170212566581926747559000694979534392034439796933335542554551981322424774631715454669002723657175134418412556653226439790475349107756702973735895193117931356004359775501074138668004417061809481535231402802835349794859992556874148430578703014721700812262863679987426564893631600671862958451813895661  
>>> phi_n = (p - 1) * (q - 1)
>>> d = pow(key.e, -1, phi_n)
>>> m = pow(c, d, key.n)
>>> hex(m)
'0x48843fc15819e23660c1cd16a573aff247f7024d18eaae397d0896f103ac'
>>> bytes.fromhex(hex(m)[2:])
b'H\x84?\xc1X\x19\xe26`\xc1\xcd\x16\xa5s\xaf\xf2G\xf7\x02M\x18\xea\xae9}\x08\x96\xf1\x03\xac'
>>> len(bytes.fromhex(hex(m)[2:]))
30

    m_str = str(m)

    m_numbers = [int(m_str[i:i+3]) for i in range(0, len(m_str), 3)]  
    flag = ''

    for m_n in m_numbers:
        list = str(bin(gen_and_check(m_n)))
        candidate = list[2::]
        candidate = candidate.zfill(8)
        flag += chr(int(candidate, 2))

    print(flag)

$ python3 solve.py
ZmxhZz1Ccm9rM25fRzRtZQ==

$ python3 solve.py | base64 -d  
flag=Brok3n_G4me