# cat blog >> /dev/brain 2> /proc/mind
cat blog >> /dev/brain 2> /proc/mind
# cat broken_rsa_source.py #!/usr/bin/env python import os from Crypto.PublicKey import RSA import SocketServer import threading import time flag = "RSA_isn't_so_great_after_all?!" class threadedserver(SocketServer.ThreadingMixIn, SocketServer.TCPServer): pass class incoming(SocketServer.BaseRequestHandler): def handle(self): cur_thread = threading.current_thread() welcome = """ ******************************************* *** Welcome to the *** *** FlAg EnCrYpTiOn SeRviCe 9000! *** ******************************************* We encrypt the flags, you get the points! """ self.request.send(welcome) rsa = RSA.generate(1024,os.urandom) n = getattr(rsa,'n') #no one will ever be able to solve our super challenge! self.request.send("To prove how secure our service is ") self.request.send("here is an encrypted flag:\n") self.request.send("==================================\n") self.request.send(hex(pow(int(flag.encode("hex"), 16),3,n))) self.request.send("\n==================================\n") self.request.send("Find the plaintext and we'll give you points\n\n") while True: self.request.send("\nNow enter a message you wish to encrypt: ") m = self.request.recv(1024) self.request.send("Your super unreadable ciphertext is:\n") self.request.send("==================================\n") self.request.send(hex(pow(int(m.encode("hex"), 16),3,n))) self.request.send("\n==================================\n") server = threadedserver(("0.0.0.0", 6666), incoming) server.timeout = 4 server_thread = threading.Thread(target=server.serve_forever) server_thread.daemon = True server_thread.start() server_thread.join() # cat crack_rsa.py #!/usr/bin/python import collections import gmpy import re import socket import time HOST = 'localhost' PORT = 6666 NC = 3 NM = 3 cf = [] n = [] def egcd(a, b): if a == 0: return (b, 0, 1) else: g, y, x = egcd(b % a, a) return (g, x - (b // a) * y, y) def modinv(a, m): g, x, y = egcd(a, m) if g != 1: return None # modular inverse does not exist else: return x % m def chinese_remainder_theorem(cf, n): if coprime(n): a0 = n[1] * n[2] a1 = n[0] * n[2] a2 = n[0] * n[1] b0 = modinv(a0, n[0]) b1 = modinv(a1, n[1]) b2 = modinv(a2, n[2]) c0 = cf[0] c1 = cf[1] c2 = cf[2] return ((a0 * b0 * c0) + (a1 * b1 * c1) + (a2 * b2 * c2)) % (n[0] * n[1] * n[2]) else: return 'The numbers are not coprimes' def coprime(n): l = len(n) for i in range(l): a = i % l b = (i + 1) % l if gmpy.gcd(n[a], n[b]) != 1: return False return True class Connection: def __init__(self, h, p, nm): self.sleep = 0.2 self.size = 50 self.nm = nm self.message = [] self.i_message = [] for i in range(self.nm): s = str(i) * self.size self.message.append(s) self.i_message.append(self.m_to_int(s)) self.server_socket = (h, p) def connect(self): self.cmessage = [ '', '', '' ] self.i_cmessage = [ '', '', '' ] self.cflag = '' self.n = '' self.client = socket.socket(socket.AF_INET, socket.SOCK_STREAM) self.client.connect(self.server_socket) def get_cipher_flag(self): self.client.recv(1024) time.sleep(self.sleep) self.cflag = int(re.search('0x.*', self.client.recv(1024)).group(0)[2:-1], 16) print 'cflag = ', self.cflag def get_cipher_message(self, num): self.client.send(self.message[num]) self.client.recv(1024) time.sleep(self.sleep) self.cmessage[num] = re.search('0x.*', self.client.recv(1024)).group(0) self.i_cmessage[num] = self.cm_to_int(self.cmessage[num]) def m_to_int(self, s): exp = 3 return pow(int(s.encode('hex'), 16), exp) def cm_to_int(self, s): return int(s[2:-1], 16) def get_gcd(self): c = collections.Counter() for i in range(self.nm): n = i % self.nm m = (i + 1) % self.nm c[gmpy.gcd(self.i_message[n] - self.i_cmessage[n], self.i_message[m] - self.i_cmessage[m])] += 1 n = c.most_common(1)[0] if n[0] > 1: print 'n = ', n[0] self.n = gmpy.mpz(n[0]) def disconnect(self): self.client.close() c = Connection(HOST, PORT, NM) for i in range(NC): c.connect() c.get_cipher_flag() for j in range(NM): c.get_cipher_message(j) c.get_gcd() cf.append(c.cflag) n.append(c.n) c.disconnect() crt = chinese_remainder_theorem(cf, n) print hex(int(gmpy.mpz(crt).root(3)[0]))[2:-1].decode('hex') # ./crack_rsa.py cflag = 183432220267576292492132231787500365567429443254723902370093717268660821440942897692891409209336083625860622526532735669405478985976131391373638097071941387759145613334518590037634953987431887257447884479468348868961 n = 135953784270768443683613403195167981915031252138094570429369041989727851055124422396867423943809003975436286026628304014780104754769108750066849076612355407811413680217618966981934851066430783270443526817656919939971313423309707876858646782024226363140350626824949333424034972566150688727067529487352636390043 cflag = 183432220267576292492132231787500365567429443254723902370093717268660821440942897692891409209336083625860622526532735669405478985976131391373638097071941387759145613334518590037634953987431887257447884479468348868961 n = 147426225645417139553342358404886645198529522490352691359839782491873450611461887111145469995954618522250637992779925978401830015610097593122018203880703073585636063945771347245716348603489552232317048688060505292755946373819909981955997660918014633102382919198924439017502469967016198925492585769516272283379 cflag = 183432220267576292492132231787500365567429443254723902370093717268660821440942897692891409209336083625860622526532735669405478985976131391373638097071941387759145613334518590037634953987431887257447884479468348868961 n = 627332965352768740770155366254106959845300172492870722009973118834731530296849175221538708067947689697177943580184423563532887600462655450044573132748970903250245024373466833416970187734469135829450190039040909806348483319266202748803421327450659922751634580246585367885974686043464239023205128753870103334908 RSA_isn't_so_great_after_all?!
cat broken_rsa_source.py
cat crack_rsa.py
./crack_rsa.py
p # prime number q # prime number n # modulus n = p * q totien(n) = (p - 1) * (q - 1) e # public key exponent 1 < e < totien(n) and gcd(e, n) = 1 d # private key exponent # Method 1 d = gmpy.invert(e, totien(n)) # Method 2 def egcd(a, b): if a == 0: return (b, 0, 1) else: g, y, x = egcd(b % a, a) return (g, x - (b // a) * y, y) def modinv(a, m): g, x, y = egcd(a, m) if g != 1: return None # modular inverse does not exist else: return x % m d = modinv(e, totien(n)) # Method 3 d = 1 while True: if (e * d - 1) % totien_n == 0: print d break else: d += 1 (e, n) # public key (d, n) # private key
p = 61 q = 53 n = 53 * 61 = 3233 totien(3233) = (53 - 1) * (61 - 1) = 3120 e = 17 d = modinv(e, totien(3233)) = 2753 (17, 3233) # public key (2753, 3233) # private key m = 65 # message c # ciphertext
c = m**e % n = pow(m, e, n) c = 65**17 % 3233 = pow(65, 17, 3233) = 2790
m = c**d % n = pow(c, d, n) m = 2790**2753 % 3233 = pow (2790, 2753, 3233) = 65 # CRT (to speed up calculation) dp = d % (p - 1) = 2753 % (61 - 1) = 53 dq = d % (q - 1) = 2753 % (53 - 1) = 49 qinv = modinv(q, p) = modinv(53, 61) = 38 m1 = c**dp % p = 2790**53 % 61 = 4 m2 = c**dq % q = 2790**49 % 53 = 12 h = (qinv * (m1 - m2)) % p = (38 * (4 - 12)) % 61 = 1 m = m2 + (h * q) = 12 + (1 * 53)= 65