#!/usr/bin/python ## OTP - Recovering the private key from a set of messages that were encrypted w/ the same private key (Many time pad attack) - crypto100-many_time_secret @ alexctf 2017 # @author intrd - http://dann.com.br/ # Original code by jwomers: https://github.com/Jwomers/many-time-pad-attack/blob/master/attack.py)
import string import collections import sets, sys
# 11 unknown ciphertexts (in hex format), all encrpyted with the same key c1 = "14f5f95b4a252948a8aef177d6c92d82e3016362bd7463f41f40a00ad9e0ccad911b959ef8dfad5f1cc4481ecb64" c2 = "06e2f65a4c256d0ba8ada164cecd329cae436069f83476e91757e91bd4a4cce2c60a8f9aac8cb14210d55253cd787c0f6a" c3 = "03f9ea574c267249b2b1ef5d91cd3c99904a3f75873871e94157df0fcbb5d1eab94f9386" ciphers = [c1, c2, c3] # The target ciphertext we want to crack target_cipher = "03f9ea574c267249b2b1ef5d91cd3c99904a3f75873871e94157df0fcbb5d1eab94f9386"
# XORs two string defstrxor(a, b): # xor two strings (trims the longer input) return"".join([chr(ord(x) ^ ord(y)) for (x, y) inzip(a, b)])
# To store the final key final_key = [None]*150 # To store the positions we know are broken known_key_positions = set()
# For each ciphertext for current_index, ciphertext inenumerate(ciphers): counter = collections.Counter() # for each other ciphertext for index, ciphertext2 inenumerate(ciphers): if current_index != index: # don't xor a ciphertext with itself for indexOfChar, char inenumerate(strxor(ciphertext.decode('hex'), ciphertext2.decode('hex'))): # Xor the two ciphertexts # If a character in the xored result is a alphanumeric character, it means there was probably a space character in one of the plaintexts (we don't know which one) if char in string.printable and char.isalpha(): counter[indexOfChar] += 1# Increment the counter at this index knownSpaceIndexes = []
# Loop through all positions where a space character was possible in the current_index cipher for ind, val in counter.items(): # If a space was found at least 7 times at this index out of the 9 possible XORS, then the space character was likely from the current_index cipher! if val >= 7: knownSpaceIndexes.append(ind) #print knownSpaceIndexes # Shows all the positions where we now know the key!
# Now Xor the current_index with spaces, and at the knownSpaceIndexes positions we get the key back! xor_with_spaces = strxor(ciphertext.decode('hex'),' '*150) for index in knownSpaceIndexes: # Store the key's value at the correct position final_key[index] = xor_with_spaces[index].encode('hex') # Record that we known the key at this position known_key_positions.add(index)
# Construct a hex key from the currently known key, adding in '00' hex chars where we do not know (to make a complete hex string) final_key_hex = ''.join([val if val isnotNoneelse'00'for val in final_key]) # Xor the currently known key with the target cipher output = strxor(target_cipher.decode('hex'),final_key_hex.decode('hex'))
print"Fix this sentence:" print''.join([char if index in known_key_positions else'*'for index, char inenumerate(output)])+"\n"
# WAIT.. MANUAL STEP HERE # This output are printing a * if that character is not known yet # fix the missing characters like this: "Let*M**k*ow if *o{*a" = "cure, Let Me know if you a" # if is too hard, change the target_cipher to another one and try again # and we have our key to fix the entire text!
#sys.exit(0) #comment and continue if u got a good key
target_plaintext = "printed on flammable material so that spies could" print"Fixed:" print target_plaintext+"\n"
e = 359050389152821553416139581503505347057925208560451864426634100333116560422313639260283981496824920089789497818520105189684311823250795520058111763310428202654439351922361722731557743640799254622423104811120692862884666323623693713 n = 26866112476805004406608209986673337296216833710860089901238432952384811714684404001885354052039112340209557226256650661186843726925958125334974412111471244462419577294051744141817411512295364953687829707132828973068538495834511391553765427956458757286710053986810998890293154443240352924460801124219510584689 c = 67743374462448582107440168513687520434594529331821740737396116407928111043815084665002104196754020530469360539253323738935708414363005373458782041955450278954348306401542374309788938720659206881893349940765268153223129964864641817170395527170138553388816095842842667443210645457879043383345869
通过c=(flag*e)%n可得
1 2 3
c = (flag * e) % n c * e^-1 = (flag * e * e^-1) % n c * e^-1 = flag % n
1 2 3 4 5 6 7
from Crypto.Util.number import * e = 359050389152821553416139581503505347057925208560451864426634100333116560422313639260283981496824920089789497818520105189684311823250795520058111763310428202654439351922361722731557743640799254622423104811120692862884666323623693713 n = 26866112476805004406608209986673337296216833710860089901238432952384811714684404001885354052039112340209557226256650661186843726925958125334974412111471244462419577294051744141817411512295364953687829707132828973068538495834511391553765427956458757286710053986810998890293154443240352924460801124219510584689 c = 67743374462448582107440168513687520434594529331821740737396116407928111043815084665002104196754020530469360539253323738935708414363005373458782041955450278954348306401542374309788938720659206881893349940765268153223129964864641817170395527170138553388816095842842667443210645457879043383345869 d=inverse(e,n) flag=(c*d)%n print(long_to_bytes(flag))