четверг, 13 марта 2014 г.

Атака удлинением сообщения

Server (python27.quals.ructf.org:12337) accepts only authorized messages.
 It works like this:

buf = c.recv(4096)

digest, msg = buf.split(" ", 1)

if (digest == md5(password+msg).hexdigest()):

  #here I send a secret

else:

  c.send("Wrong signature\n")
 

You have intercepted one authorized message: "b34c39b9e83f0e965cf392831b3d71b8 do test connection".
Construct your own authorized message! Answer starts with 'RUCTF_'

Почитать про атаку и ее описание можно на http://en.wikipedia.org/wiki/Length_extension_attack
А я ограничу свое повестование описанием самой сути задачи и решения.

Дан сервер, который запрашивает какое-либо сообщение и подпись этого сообщения.
Подпись формируется md5(password+msg). При этом password нам неизвестен, а значит сконструировать валидную подпись не получится.

Но у нас есть сообщение и валидная подпись этого сообщения. Используя данную атаку, которая описана в вики, можно, имея подпись для MSG, получить подпись для MSG+MSG_2, где MSG_2 любой текст. При этом password мы не узнаем, но подпись будет верной.

Остается лишь найти в интернете скрипт и написать эксплойт.


"""
MD5C.C - RSA Data Security, Inc., MD5 message-digest algorithm

Copyright (C) 1991-2, RSA Data Security, Inc. Created 1991. All
rights reserved.

License to copy and use this software is granted provided that it
is identified as the "RSA Data Security, Inc. MD5 Message-Digest
Algorithm" in all material mentioning or referencing this software
or this function.

License is also granted to make and use derivative works provided
that such works are identified as "derived from the RSA Data
Security, Inc. MD5 Message-Digest Algorithm" in all material
mentioning or referencing the derived work.

RSA Data Security, Inc. makes no representations concerning either
the merchantability of this software or the suitability of this
software for any particular purpose. It is provided "as is"
without express or implied warranty of any kind.

These notices must be retained in any copies of any part of this
documentation and/or software.
"""
import socks
# Constants for MD5Transform routine.

S11 = 7
S12 = 12
S13 = 17
S14 = 22
S21 = 5
S22 = 9
S23 = 14
S24 = 20
S31 = 4
S32 = 11
S33 = 16
S34 = 23
S41 = 6
S42 = 10
S43 = 15
S44 = 21

PADDING = "\x80" + 63*"\0"   # do not overlook first byte again :-)

# F, G, H and I are basic MD5 functions
def F(x, y, z): return (((x) & (y)) | ((~x) & (z)))

def G(x, y, z): return (((x) & (z)) | ((y) & (~z)))

def H(x, y, z): return ((x) ^ (y) ^ (z))

def I(x, y, z): return((y) ^ ((x) | (~z)))

# ROTATE_LEFT rotates x left n bits.
def ROTATE_LEFT(x, n):
    x = x & 0xffffffffL   # make shift unsigned
    return (((x) << (n)) | ((x) >> (32-(n)))) & 0xffffffffL

# FF, GG, HH, and II transformations for rounds 1, 2, 3, and 4.
# Rotation is separate from addition to prevent recomputation.
def FF(a, b, c, d, x, s, ac):
    a = a + F ((b), (c), (d)) + (x) + (ac)
    a = ROTATE_LEFT ((a), (s))
    a = a + b
    return a # must assign this to a

def GG(a, b, c, d, x, s, ac):
    a = a + G ((b), (c), (d)) + (x) + (ac)
    a = ROTATE_LEFT ((a), (s))
    a = a + b
    return a # must assign this to a

def HH(a, b, c, d, x, s, ac):
    a = a + H ((b), (c), (d)) + (x) + (ac)
    a = ROTATE_LEFT ((a), (s))
    a = a + b
    return a # must assign this to a

def II(a, b, c, d, x, s, ac):
    a = a + I ((b), (c), (d)) + (x) + (ac)
    a = ROTATE_LEFT ((a), (s))
    a = a + b
    return a # must assign this to a


class md5:
    def __init__(self, initial=None):
        self.count = 0L
        self.state = (0x67452301L,
                      0xefcdab89L,
                      0x98badcfeL,
                      0x10325476L,)
        self.buffer = ""
        if initial:
            self.update(initial)
            

    def update(self, input):
        """
        MD5 block update operation. Continues an MD5 message-digest
        operation, processing another message block, and updating the
        context.
        """
        inputLen = len(input)
        index = int(self.count >> 3) & 0x3F

        # Update number of bits 
        self.count = self.count + (inputLen << 3)
        print("count = %s" % repr(self.count))
        
        partLen = 64 - index

        # Transform as many times as possible.
        if inputLen >= partLen:
            self.buffer = self.buffer[:index] + input[:partLen]
            self.transform(self.buffer)
            i = partLen
            while i + 63 < inputLen:
                self.transform(input[i:i+64])
                i = i + 64
            index = 0
        else:
            i = 0

        # Buffer remaining input
        self.buffer = self.buffer[:index] + input[i:inputLen]

        
    def final(self):
        """
        MD5 finalization. Ends an MD5 message-digest operation, 
        writing the message digest and zeroizing the context.
        """
        # Save number of bits
        bits = Encode((self.count & 0xffffffffL, self.count>>32), 8)
        
        # Pad out to 56 mod 64
        index = int((self.count >> 3) & 0x3f)

        if index < 56:
            padLen = (56 - index)
        else:
            padLen = (120 - index)
        
        # Append padding
        self.update(PADDING[:padLen])

        # Append bits
        self.update(bits)
        
        # Store state in digest
        digest = Encode(self.state, 16)

        # Zeroize sensitive information
        self.__dict__.clear()
        return digest
    
    digest = final  # alias

    def transform(self, block):
        """ MD5 basic transformation. Transforms state based on block """
        a, b, c, d = state = self.state

        x = Decode(block, 64)

        # Round 1
        a = FF (a, b, c, d, x[ 0], S11, 0xd76aa478)#; /* 1 */
        d = FF (d, a, b, c, x[ 1], S12, 0xe8c7b756)#; /* 2 */
        c = FF (c, d, a, b, x[ 2], S13, 0x242070db)#; /* 3 */
        b = FF (b, c, d, a, x[ 3], S14, 0xc1bdceee)#; /* 4 */
        a = FF (a, b, c, d, x[ 4], S11, 0xf57c0faf)#; /* 5 */
        d = FF (d, a, b, c, x[ 5], S12, 0x4787c62a)#; /* 6 */
        c = FF (c, d, a, b, x[ 6], S13, 0xa8304613)#; /* 7 */
        b = FF (b, c, d, a, x[ 7], S14, 0xfd469501)#; /* 8 */
        a = FF (a, b, c, d, x[ 8], S11, 0x698098d8)#; /* 9 */
        d = FF (d, a, b, c, x[ 9], S12, 0x8b44f7af)#; /* 10 */
        c = FF (c, d, a, b, x[10], S13, 0xffff5bb1)#; /* 11 */
        b = FF (b, c, d, a, x[11], S14, 0x895cd7be)#; /* 12 */
        a = FF (a, b, c, d, x[12], S11, 0x6b901122)#; /* 13 */
        d = FF (d, a, b, c, x[13], S12, 0xfd987193)#; /* 14 */
        c = FF (c, d, a, b, x[14], S13, 0xa679438e)#; /* 15 */
        b = FF (b, c, d, a, x[15], S14, 0x49b40821)#; /* 16 */

        # Round 2 
        a = GG (a, b, c, d, x[ 1], S21, 0xf61e2562)#; /* 17 */
        d = GG (d, a, b, c, x[ 6], S22, 0xc040b340)#; /* 18 */
        c = GG (c, d, a, b, x[11], S23, 0x265e5a51)#; /* 19 */
        b = GG (b, c, d, a, x[ 0], S24, 0xe9b6c7aa)#; /* 20 */
        a = GG (a, b, c, d, x[ 5], S21, 0xd62f105d)#; /* 21 */
        d = GG (d, a, b, c, x[10], S22,  0x2441453)#; /* 22 */
        c = GG (c, d, a, b, x[15], S23, 0xd8a1e681)#; /* 23 */
        b = GG (b, c, d, a, x[ 4], S24, 0xe7d3fbc8)#; /* 24 */
        a = GG (a, b, c, d, x[ 9], S21, 0x21e1cde6)#; /* 25 */
        d = GG (d, a, b, c, x[14], S22, 0xc33707d6)#; /* 26 */
        c = GG (c, d, a, b, x[ 3], S23, 0xf4d50d87)#; /* 27 */
        b = GG (b, c, d, a, x[ 8], S24, 0x455a14ed)#; /* 28 */
        a = GG (a, b, c, d, x[13], S21, 0xa9e3e905)#; /* 29 */
        d = GG (d, a, b, c, x[ 2], S22, 0xfcefa3f8)#; /* 30 */
        c = GG (c, d, a, b, x[ 7], S23, 0x676f02d9)#; /* 31 */
        b = GG (b, c, d, a, x[12], S24, 0x8d2a4c8a)#; /* 32 */

        # Round 3
        a = HH (a, b, c, d, x[ 5], S31, 0xfffa3942)#; /* 33 */
        d = HH (d, a, b, c, x[ 8], S32, 0x8771f681)#; /* 34 */
        c = HH (c, d, a, b, x[11], S33, 0x6d9d6122)#; /* 35 */
        b = HH (b, c, d, a, x[14], S34, 0xfde5380c)#; /* 36 */
        a = HH (a, b, c, d, x[ 1], S31, 0xa4beea44)#; /* 37 */
        d = HH (d, a, b, c, x[ 4], S32, 0x4bdecfa9)#; /* 38 */
        c = HH (c, d, a, b, x[ 7], S33, 0xf6bb4b60)#; /* 39 */
        b = HH (b, c, d, a, x[10], S34, 0xbebfbc70)#; /* 40 */
        a = HH (a, b, c, d, x[13], S31, 0x289b7ec6)#; /* 41 */
        d = HH (d, a, b, c, x[ 0], S32, 0xeaa127fa)#; /* 42 */
        c = HH (c, d, a, b, x[ 3], S33, 0xd4ef3085)#; /* 43 */
        b = HH (b, c, d, a, x[ 6], S34,  0x4881d05)#; /* 44 */
        a = HH (a, b, c, d, x[ 9], S31, 0xd9d4d039)#; /* 45 */
        d = HH (d, a, b, c, x[12], S32, 0xe6db99e5)#; /* 46 */
        c = HH (c, d, a, b, x[15], S33, 0x1fa27cf8)#; /* 47 */
        b = HH (b, c, d, a, x[ 2], S34, 0xc4ac5665)#; /* 48 */

        # Round 4 
        a = II (a, b, c, d, x[ 0], S41, 0xf4292244)#; /* 49 */
        d = II (d, a, b, c, x[ 7], S42, 0x432aff97)#; /* 50 */
        c = II (c, d, a, b, x[14], S43, 0xab9423a7)#; /* 51 */
        b = II (b, c, d, a, x[ 5], S44, 0xfc93a039)#; /* 52 */
        a = II (a, b, c, d, x[12], S41, 0x655b59c3)#; /* 53 */
        d = II (d, a, b, c, x[ 3], S42, 0x8f0ccc92)#; /* 54 */
        c = II (c, d, a, b, x[10], S43, 0xffeff47d)#; /* 55 */
        b = II (b, c, d, a, x[ 1], S44, 0x85845dd1)#; /* 56 */
        a = II (a, b, c, d, x[ 8], S41, 0x6fa87e4f)#; /* 57 */
        d = II (d, a, b, c, x[15], S42, 0xfe2ce6e0)#; /* 58 */
        c = II (c, d, a, b, x[ 6], S43, 0xa3014314)#; /* 59 */
        b = II (b, c, d, a, x[13], S44, 0x4e0811a1)#; /* 60 */
        a = II (a, b, c, d, x[ 4], S41, 0xf7537e82)#; /* 61 */
        d = II (d, a, b, c, x[11], S42, 0xbd3af235)#; /* 62 */
        c = II (c, d, a, b, x[ 2], S43, 0x2ad7d2bb)#; /* 63 */
        b = II (b, c, d, a, x[ 9], S44, 0xeb86d391)#; /* 64 */

        self.state = (0xffffffffL & (state[0] + a),
                      0xffffffffL & (state[1] + b),
                      0xffffffffL & (state[2] + c),
                      0xffffffffL & (state[3] + d),)

        # Zeroize sensitive information.
        del x

# Some helper functions to decode and encode binary data
import struct, string

def Encode(input, len):
    k = len >> 2
    res = apply(struct.pack, ("%iI" % k,) + tuple(input[:k]))
    return string.join(res, "")

def Decode(input, len):
    k = len >> 2
    res = struct.unpack("%iI" % k, input[:len])
    return list(res)





# =================
# = Spoofing Code =
# =================
def spoof_digest(originalDigest, originalLen, spoofMessage=""):
    # first decode digest back into state tuples
    state = Decode(originalDigest, 16)
    
    # generate a seed md5 object
    spoof = md5()
    
    # seed the count variable for calculation of index, padLen, and bits
    spoof.count += originalLen << 3
    
    # calculate some variables to generate the original padding
    index = int((spoof.count >> 3) & 0x3f)
    padLen = (56 - index) if index < 56 else (120 - index)
    bits = Encode((spoof.count & 0xffffffffL, spoof.count>>32), 8)

    # construct the original padding
    padding = PADDING[:padLen]

    # augment the count with the new padding and trailing bits
    spoof.count += len(padding) << 3
    spoof.count += len(bits) << 3
    spoof.state = state
    
    # run an update
    spoof.update(spoofMessage)
    
    # We now have a digest of the original secret + message + some_padding
    return (spoof.digest(), padding + bits)

def test_md5_matches_stdlib():
    from hashlib import md5 as md5stdlib
    std_signature = md5stdlib('hello').digest()
    this_md5_signature = md5('hello').digest()
    assert this_md5_signature == std_signature
    
def test_spoofing():
    originalMsg = "" + "do test connection"
    appendedMsg = "123"
    
    # This is the signature that a legitimate user sends
    # over the wire in clear text. 
    originalSignature = "b34c39b9e83f0e965cf392831b3d71b8".decode('hex')
    
    # This is how an attacker would spoof the signature where,
    # the message ==  originalMsg + padbits + appendedMsg .
    # Notice that this method implies that the attacker
    # knows the original length of the "secret" ... 
    # Most apis such as Flickr assign secrets that are of
    # uniform length for all of their api users.
    
    #spoofSignature, padbits = spoof_digest(originalSignature, i, appendedMsg)
    socket = socks.socksocket()
    import time
    #socket.connect(('python27.quals.ructf.org' , 12337))
    for i in range(len(originalMsg),len(originalMsg)+65):
        socket = socks.socksocket()
        socket.connect(('python27.quals.ructf.org' , 12337))
        spoofSignature, padbits = spoof_digest(originalSignature, i, appendedMsg)
        print spoofSignature.encode('hex')
        socket.send(spoofSignature.encode('hex')+" do test connection"+padbits+"123")
        print socket.recv(1024)
        time.sleep(1)
        socket.close()
    
    # This is how a legitimate user would construct the
    # a signature when message == originalMsg + padbits + appendedMsg
    testSignature = md5(originalMsg + padbits + appendedMsg).digest()
    
    # make sure the spoof signature and the test signature match.
    # if, this passes, we've successfully constructed a spoofed message
    # of the form: secret + orginal_message + padding + appended_message
    # without actually knowing the secret.
    #assert testSignature == spoofSignature
    #return testSignature.encode('hex')
    
if __name__=="__main__":
    print test_spoofing()

Зачем я это написал? Да просто чтобы познакомить читателей с интересным методом.
Почему не описал саму атаку? А зачем? Я и так привел ссылку на подробное и хорошее описание.
Это что-то вроде репоста :) Я хочу вас познакомить с классной темой!

вторник, 4 марта 2014 г.

Тест на простоту

Тест Миллера-Рабина

import random, sys                             

def miller_rabin_pass(a, s, d, n):
    a_to_power = pow(a, d, n)
    if a_to_power == 1:
        return True
    for i in xrange(s-1):
        if a_to_power == n - 1:
            return True
        a_to_power = (a_to_power * a_to_power) % n
    return a_to_power == n - 1

def miller_rabin(n):
    d = n - 1
    s = 0
    while d % 2 == 0:
        d &gt;&gt;= 1
        s += 1

    for repeat in xrange(20):
        a = 0
        while a == 0:
            a = random.randrange(n)
        if not miller_rabin_pass(a, s, d, n):
            return False
    return True

RuCTF quals-2013. Crypto 200

Задание

Дан файл на питоне.
def crypt(open_text, public_key):
  bts = []
  [bts.extend([int(b) for b in '00000000'[len(bin(ord(c))[2:]):] + bin(ord(c))[2:]]) for c in open_text]
  return [sum(map(lambda x: x[0] * x[1] ,zip(blk, public_key))) for blk in [bts[i * 128:(i+1) * 128] for i in range(len(open_text) // 16)]] 

def generate_public_key(private_key):   
  n = 199285318978668966527551342512997250816637709274749259983292077699440369
  t = 32416190071
  return list(map(lambda x: (t * x) % n, private_key))
public_key = [1050809378719198985041, 2101618757438397970082, 6304856272315193910246, 18914568816945581730738, 56743706450836745192214, 170231119352510235576642, 510693358057530706729926, 1532080074172592120189778, 4596240222517776360569334, 13788720667553329081708002, 41366162002659987245124006, 124098486007979961735372018, 372295458023939885206116054, 1116886374071819655618348162, 3350659122215458966855044486, 10051977366646376900565133458, 30155932099939130701695400374, 90467796299817392105086201122, 271403388899452176315258603366, 814210166698356528945775810098, 2442630500095069586837327430294, 7327891500285208760511982290882, 21983674500855626281535946872646, 65951023502566878844607840617938, 197853070507700636533823521853814, 593559211523101909601470565561442, 1780677634569305728804411696684326, 5342032903707917186413235090052978, 16026098711123751559239705270158934, 48078296133371254677719115810476802, 144234888400113764033157347431430406, 432704665200341292099472042294291218, 1298113995601023876298416126882873654, 3894341986803071628895248380648620962, 11683025960409214886685745141945862886, 35049077881227644660057235425837588658, 105147233643682933980171706277512765974, 315441700931048801940515118832538297922, 946325102793146405821545356497614893766, 2838975308379439217464636069492844681298, 8516925925138317652393908208478534043894, 25550777775414952957181724625435602131682, 76652333326244858871545173876306806395046, 229956999978734576614635521628920419185138, 689870999936203729843906564886761257555414, 2069612999808611189531719694660283772666242, 6208838999425833568595159083980851317998726, 18626516998277500705785477251942553953996178, 55879550994832502117356431755827661861988534, 167638652984497506352069295267482985585965602, 502915958953492519056207885802448956757896806, 1508747876860477557168623657407346870273690418, 4526243630581432671505870972222040610821071254, 13578730891744298014517612916666121832463213762, 40736192675232894043552838749998365497389641286, 122208578025698682130658516249995096492168923858, 366625734077096046391975548749985289476506771574, 1099877202231288139175926646249955868429520314722, 3299631606693864417527779938749867605288560944166, 9898894820081593252583339816249602815865682832498, 29696684460244779757750019448748808447597048497494, 89090053380734339273250058346246425342791145492482, 267270160142203017819750175038739276028373436477446, 801810480426609053459250525116217828085120309432338, 2405431441279827160377751575348653484255360928297014, 7216294323839481481133254726045960452766082784891042, 21648882971518444443399764178137881358298248354673126, 64946648914555333330199292534413644074894745064019378, 194839946743665999990597877603240932224684235192058134, 584519840230997999971793632809722796674052705576174402, 1753559520692993999915380898429168390022158116728523206, 5260678562078981999746142695287505170066474350185569618, 15782035686236945999238428085862515510199423050556708854, 47346107058710837997715284257587546530598269151670126562, 142038321176132513993145852772762639591794807455010379686, 426114963528397541979437558318287918775384422365031139058, 1278344890585192625938312674954863756326153267095093417174, 3835034671755577877814938024864591268978459801285280251522, 11505104015266733633444814074593773806935379403855840754566, 34515312045800200900334442223781321420806138211567522263698, 103545936137400602701003326671343964262418414634702566791094, 310637808412201808103009980014031892787255243904107700373282, 931913425236605424309029940042095678361765731712323101119846, 2795740275709816272927089820126287035085297195136969303359538, 8387220827129448818781269460378861105255891585410907910078614, 25161662481388346456343808381136583315767674756232723730235842, 75484987444165039369031425143409749947303024268698171190707526, 226454962332495118107094275430229249841909072806094513572122578, 679364886997485354321282826290687749525727218418283540716367734, 2038094660992456062963848478872063248577181655254850622149103202, 6114283982977368188891545436616189745731544965764551866447309606, 18342851948932104566674636309848569237194634897293655599341928818, 55028555846796313700023908929545707711583904691880966798025786454, 165085667540388941100071726788637123134751714075642900394077359362, 495257002621166823300215180365911369404255142226928701182232078086, 1485771007863500469900645541097734108212765426680786103546696234258, 4457313023590501409701936623293202324638296280042358310640088702774, 13371939070771504229105809869879606973914888840127074931920266108322, 40115817212314512687317429609638820921744666520381224795760798324966, 120347451636943538061952288828916462765233999561143674387282394974898, 361042354910830614185856866486749388295701998683431023161847184924694, 1083127064732491842557570599460248164887105996050293069485541554774082, 3249381194197475527672711798380744494661317988150879208456624664322246, 9748143582592426583018135395142233483983953964452637625369873992966738, 29244430747777279749054406185426700451951861893357912876109621978900214, 87733292243331839247163218556280101355855585680073738628328865936700642, 63914557751326551213938313155843053250929047765471955901694520110661557, 191743673253979653641814939467529159752787143296415867705083560331984671, 176660381804601027870342133376592977625086011339749083148666525597073275, 131410507456465150555923715103784431241982615469748729479415421392339087, 194946203390726485140219802798356042909310137134496928454954186477576892, 186267972214841522365556723369073627094654992853992265398278404033849938, 160233278687186634041567485081226379650689560012478276228251056702669076, 82129198104221969069599770217684637318793261487936308718169014709126490, 47102275333996940681247968140056661139742075189059666171214966427939101, 141306826001990822043743904420169983419226225567178998513644899283817303, 25349840048634533076129028234515448624403258152038475574350542452571171, 76049520145903599228387084703546345873209774456115426723051627357713513, 28863241459041831157609911597641786802991614093597020185862804373700170, 86589724377125493472829734792925360408974842280791060557588413121100510, 60483854152707513890937861865778830410286817567623921689473161663861161, 181451562458122541672813585597336491230860452702871765068419484991583483, 145784049417029691963338071766014972059305939559116775238674299575869711, 38781510293751142834911530272050414544642400127851805749438743328728395, 116344530881253428504734590816151243633927200383555417248316229986185185, 149748273665091318986652429935456480085143891875916991761656612259115186, 50674183037936023904854604780374938622156257078252455318385681378464820, 152022549113808071714563814341124815866468771234757365955157044135394460]   
cipher_text = [
        1387977778999926469357780220487630125151962348185941993910077394771302677,
        1192236960845781949613172279312582839292898077268409678421304772227241438,
        1295152741157953792099179799985052248167548374589648818528421499250916999,
        828724787424187908000366458781164595076558885463707900320215679908512646,
        1179926879709109047038661681316962368287877340885819899201698611790531134,
        965171312356484716595815857561729919489896088681139239093293829323154838,
        1099367377207651843612375443021502714028353049437532392256489525051038347,
        1374891605015623267623322424512489936836885983493815443812918444687247914,
        1152880248428103510879661300981452627677389745079857275081612568623556291,
        962409003220820525413536841942678826309419979028794415812582008820263317


Первая функция генерирует публичные ключи по приватным.
Принцип прост – умножение по модулю. Но мы решили, что эта функция не нужна.

Вторая дополняет бинарное представление символов текста ведущими нулями, а затем производит действия над блоками по 16 байт. Выходит, что искомый текст имеет длину 16*10 ascii символов.
Каждый блок из 16 байт (128 бит) сопоставляется массиву из 128 чисел (public_key).

Каждый бит умножается на элемент публичного ключа с тем же индексом, результаты складываются.
Очевидно, что в результате в шифротексте мы получим сумму некоторых элементов публичного ключа.

Мы заметили, что

1050809378719198985041 = 32416190071^2

2101618757438397970082 = 32416190071^2 * 2

6304856272315193910246 = 32416190071^2 * 2 * 3

Pkn = 32416190071^2 * 2 * 3 ^ n

Странно, но начиная со 106 до 127, эта закономерность не соблюдается (мы так решили).

По-этому мы брутфорсили 24 символа (2 слева и 22 справа). Для них вычисляли сумму произведений.
Затем из N вычитали данную сумму и получали результат, который является по сути суммой элементов публичного ключа, которые удовлетворяют нашей формуле. Значит можно разделить само (n-s) и все числа на t*t*2.
Получаем, что новая N2 = 3^a+3^b+…3^z. Где неизвестны степени и число элементов.
Теперь будем делить последовательно на 3. Как только деление невозможно – мы нашли показатель степени и можно его вытащить из суммы: получить N3 = N2 – 3^a.
Повторяем данные действия для получения всех коэффициентов.
Если они не повторяются – вариант валидный. Остается только взять элементы public_key[a],…public_key[z] и поставить для них в ответе 1, для незадействованных – 0.
Таким образом для каждого из 2^24 итераций перебора мы находим разложение, если оно корректно (степени не повторяются) – выводим на экран бинарную строку.
Сумбурно, но лучше видно в коде.
for i in range(0, 2**24):

    s = 0

    num = '000000000000000000000000'[len(bin(i)[2:]):] + bin(i)[2:]

    for k in range(0, 22):

        s += int(num[k]) * public_key[106 + k]



    s += int(num[22]) * public_key[0]

    s += int(num[23]) * public_key[1]



    c1 = cipher_text[7] - s

    if c1 &lt; 0:

        continue



    c1 /= t*t

    c1 /= 2

    indices = []



    a = 0

    cc = c1

    zeros = 0

    bad = False



    while c1 &gt; 0:

        if c1 % 3 == 0:

            zeros += 1

            c1 /= 3

        else:

            if len(indices) and indices[a-1] == zeros:

                bad = True

                break

            else:

                indices.append(zeros)



            a += 1

            cc -= 3**(zeros)

            zeros = 0

            c1 = cc



    if not bad:

        print indices

        print num

        print '------------------'

Ответ: bf145f32d9637c37de3cb5b470b2c44f8e466bc26e06725ac1517006ab70eac23907a37da8715981c7de813dc03f8104381eadf57d50dc4841d7956fffcd22eefe8ec62e9dea680f78d18352b4bb3ec2