Writeup crypto MPRSA CTFZone2017

Райтап Crypto таска MPRSA от тиммейта Xelentra.

Задание было:

We suspect that one of the candidates plans to bribe people in order to get more votes. We have intercepted a part of his correspondence but, unfortunately, all messages are encrypted. Our man from this election campaign has informed us that they use MPRSA cryptosystem for secure communication.

crypto200.zip [2,89 Kb] (cкачиваний: 32)

Решение:

В скаченном архиве 3 файла:
- скрипт на питоне
- зашифрованный файл
- файл, содержащий значения n и e

1. Изучив скрипт, видим, что для генерации ключей используются 4 простых числа. Обозначим их как Р0, Р1, Р2, Р3. Эти простые числа вычисляются по формуле:

P[i] = next_prime ( P[i-1] * delta )

Дальше из этих простых чисел вычисляются n, e и d. Число d вычисляется так:

for d_next in count(int(pow(P[0] // 2, 0.5)), -1):
            g, e, __ = gcdext(d_next, phi)
            if (1 < e < n) and (g == 1) and (gcd(phi, e) == 1):
                d = d_next
                break

2. Идем на сайт http://factordb.com и пытаемся факторизовать n. Оно там успешно факторизуется. Получили 2 простых числа. Обозначим их Т1 и Т2:



3. Видим, что длины полученных простых чисел примерно равны. Так как из кода очевидно, что

Р0 <P1 <P2 <P3 
n = P0 * P1 * P2 * P3 = T1 * T2

=>

Т1 = Р0 * Р3
Т2 = Р1 * Р2

и

P2 = next_prime(P1 * delta) => 
P2 > P1 * delta => 
P2^2> T2 delta => 
P2 > sqrt(T2 * delta)

Из этого находим P0, P1, P2, P3, d, и расшифровываем сообщение:

#!/usr/bin/env python
from binascii import hexlify, unhexlify
from gmpy2 import next_prime, powmod, gcdext, gcd, isqrt
from itertools import count

e = 2968282037100353640375137899109790499983904510372252123726372200136866453960017151334469454219618530252326391316368089337062513360207381202191915473462935477137523455963250056561696664667826520897145326882242932509636924316993816382503962649302107865422204292490659961123103322081852240437978613121365781016988448211321349469941008479597808471102164820173139919110860676464533506147455712945961147297193425603466185665772219928497258618754492859488589873906043003885893571962433509510568617898956135134801893952671289895841202079907023382879176353447845431980339763701845065932967492613174149948295178658632744337984598033199716909609691917091599333032421515584590767434316739374277008976624091929263313294017958203501962609986428734553144207841375915976037349385525685765751825435583700725710652618107250634373424713513298201017768173878869803169781015337283490319756398578109078482368725206020186761161884650413182297877151106135232838271785994275915310662858329477083914589917431343036266926436535406078268574331773960697696088892795445640924833807153106889785640164637689271399503064510417142492169690916011945805675154490404590528925067599406358567902459063109040410209462273031696409389388590120586013927889551821936657759836121166591
n = 7514486184413883943206134802309178399244378977612173666918494750761691891054947551148635071227769468578429057411933207521812645312852372491525360936618326543031520002708891330196401800722400435500157085990690437665009726219084442021182850506847121543952655588437818213790488615953323918596261471907835421407596459273791581399309405067626383928217548743866594178747621345881632069955681378662964970779524097614470204109881600043967504127490912520547758072473768719527077924134830122844355992675524808082077564650441063165395654489609498673176326527753016138066814814395200582603579511246113422000711435941608107654792503944786693356696589418688102700165482722623897706829970814110646089600275631212777003792683291735426294012686607809533096193939103941428766195023630255837719510277444701463006437791991196936648896229397094403915485049521731674097516242423233615004601202795680477677383876821794953563585797462940468885019612996080647173400509657498552114237186425176692867162493697752241051962151120715653607272964311445754089586884116532125369172407750688737448422035240971409748803419916890500367552066268915926436633178471526464741419410486387714614840372951024874043659727111073041432865136565615528171567027369016567760790667844170057
c = 4990981759460304744105598767593686181405870005282225829795794541021226151966053079510943795109726609634828370167775307839662644021918767556530119412853816585221569546843939870445288438295880322602517246037112564416212745954141726471664361647045729235670622890953655065235230427298013906810014221648290750692583336186843003229107021202513937560627163229698907224982160099413064560450430189221548918249561722797270239205285019947483419790983776163671611001827036804081081707549809205146146016914228431689911951835061650007130105435596899572248580145216361550470379538250892374083206633208114199207657470199269462010122511529769658733474277302308656490658251694852119519651331026206905848184310474442594518003923697214854504891077728222935182875777284193900483103844390422979429620136337089544700764854729601666550485708645758202313582038929079609869996469534041940940326632417337431671554125949585769777514656385405640728690453834779703498214246941789126527089991023766694976273980553865664242840580534044580685023115108182135139502041838131616984809782973256326815445038141870218251128685050551152554710812132312358766591390023888015234480632150114384947814031965110524912964541892010650475016456100706107619225121444952046171313017830946278
T1 = 86686136056545304660994252432156625773889066120498168631765739416745482493422987585296192063723736599263002976567595657636575621223824796036376969022114262822476015189850335269173530996691468705957636088921107674849266001665959963924041156092676589677858275687705781389349325292821902667932773664074397025014885859531985374331363919370302063677714826493469850237895535599734162522545523612723105523954370722461520363868871831877731975713014099237185479936897127467760814257390477172614268597532085496975182534809762289121382430941346377303547604540401781187289401735594268644458343791158899326073313144167027058457823531
T2 = 86686136056545304660994252432156625773889066120498168631765739416745482493422987585296192063723736599263002976567595657636575621223824796036376969022114262822476015189850335269173530996691468705957636088921107674849266001665959963924041156092676589677858275687705781389349325292821902667932773664074397025057056395971127798212868512036542986007381764450802738622888457263247853466350831762343657190118694660520926555651420001826960963517554742865635266192601411342660123373292705629287891375739175779053722758700760074451754576829084967851492233558979316397070894234154863263130900750980110998751294240297623797935181147

def findP2AndDelta():
    for delta in range(5, 16):
        pre_P2 = isqrt(T2 * delta)
        for i in range(10):
            pre_P2 = next_prime(pre_P2)
            if (T2 % pre_P2 == 0):
                print '[v] Found P2 = ', pre_P2
                print '[v] Found delta = ', delta             
                return pre_P2, delta

def findP1(P2):
    P1 = T2 / P2
    print '[v] Found P1 = ', P1
    return P1

def findP3(P2, delta):
    P3 = next_prime(P2 * delta)
    print '[v] Found P3 = ', P3
    return P3

def findP0(P3):
    P0 = T1 / P3
    print '[v] Found P0 = ', P0
    return P0

def findD(P):
    phi = compute_phi(P)
    for d_next in count(int(pow(P[0] // 2, 0.5)), -1):
        g, e, __ = gcdext(d_next, phi)
        if (1 < e < n) and (g == 1) and (gcd(phi, e) == 1):        
            print '[v] Found d = ', d_next
            return d_next

def compute_phi(primes):
        phi = 1
        for prime in primes:
            phi *= (prime - 1)
        return phi

def decode_message(data):
    return unhexlify(format(data, "x"))

def decryption(ctext, d, n):
    data = powmod(ctext, d, n)
    return decode_message(data)

P2, delta = findP2AndDelta()
P1 = findP1(P2)
P3 = findP3(P2, delta)
P0 = findP0(P3)
P = [P0, P1, P2, P3]
d = findD(P)
print '================='
print decryption(c, d, n)
print '================='

скачать dle 10.5фильмы бесплатно