CTF日本語サイト

MPRSA

CRYPTO

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

• data.enc
• mprsa.py
• public.txt

from binascii import hexlify, unhexlify

from fractions import Fraction

def decode_message(data):

    if len(format(data, "x")) % 2 == 1:

        return 'ng'

    return unhexlify(format(data, "x"))

def decryption(ctext, d, n):

    data = pow(ctext, d, n)

    return decode_message(data)

def continued_fractions(n,e):

cf = [0]

while e != 0:

cf.append(int(n/e))

N = n

n = e

e = N%e

return cf

def calcKD(cf, ct, n):

kd = list()

for i in range(1,len(cf)+1):

tmp = Fraction(0)

for j in cf[1:i][::-1]:

tmp = 1/(tmp+j)

ptext = decryption(ct, tmp.denominator, n)

if 'ctfzone{' in ptext:

print ptext

break

kd.append((tmp.numerator,tmp.denominator))

return kd

n = 7514486184413883943206134802309178399244378977612173666918494750761691891054947551148635071227769468578429057411933207521812645312852372491525360936618326543031520002708891330196401800722400435500157085990690437665009726219084442021182850506847121543952655588437818213790488615953323918596261471907835421407596459273791581399309405067626383928217548743866594178747621345881632069955681378662964970779524097614470204109881600043967504127490912520547758072473768719527077924134830122844355992675524808082077564650441063165395654489609498673176326527753016138066814814395200582603579511246113422000711435941608107654792503944786693356696589418688102700165482722623897706829970814110646089600275631212777003792683291735426294012686607809533096193939103941428766195023630255837719510277444701463006437791991196936648896229397094403915485049521731674097516242423233615004601202795680477677383876821794953563585797462940468885019612996080647173400509657498552114237186425176692867162493697752241051962151120715653607272964311445754089586884116532125369172407750688737448422035240971409748803419916890500367552066268915926436633178471526464741419410486387714614840372951024874043659727111073041432865136565615528171567027369016567760790667844170057

e = 2968282037100353640375137899109790499983904510372252123726372200136866453960017151334469454219618530252326391316368089337062513360207381202191915473462935477137523455963250056561696664667826520897145326882242932509636924316993816382503962649302107865422204292490659961123103322081852240437978613121365781016988448211321349469941008479597808471102164820173139919110860676464533506147455712945961147297193425603466185665772219928497258618754492859488589873906043003885893571962433509510568617898956135134801893952671289895841202079907023382879176353447845431980339763701845065932967492613174149948295178658632744337984598033199716909609691917091599333032421515584590767434316739374277008976624091929263313294017958203501962609986428734553144207841375915976037349385525685765751825435583700725710652618107250634373424713513298201017768173878869803169781015337283490319756398578109078482368725206020186761161884650413182297877151106135232838271785994275915310662858329477083914589917431343036266926436535406078268574331773960697696088892795445640924833807153106889785640164637689271399503064510417142492169690916011945805675154490404590528925067599406358567902459063109040410209462273031696409389388590120586013927889551821936657759836121166591

ct = 4990981759460304744105598767593686181405870005282225829795794541021226151966053079510943795109726609634828370167775307839662644021918767556530119412853816585221569546843939870445288438295880322602517246037112564416212745954141726471664361647045729235670622890953655065235230427298013906810014221648290750692583336186843003229107021202513937560627163229698907224982160099413064560450430189221548918249561722797270239205285019947483419790983776163671611001827036804081081707549809205146146016914228431689911951835061650007130105435596899572248580145216361550470379538250892374083206633208114199207657470199269462010122511529769658733474277302308656490658251694852119519651331026206905848184310474442594518003923697214854504891077728222935182875777284193900483103844390422979429620136337089544700764854729601666550485708645758202313582038929079609869996469534041940940326632417337431671554125949585769777514656385405640728690453834779703498214246941789126527089991023766694976273980553865664242840580534044580685023115108182135139502041838131616984809782973256326815445038141870218251128685050551152554710812132312358766591390023888015234480632150114384947814031965110524912964541892010650475016456100706107619225121444952046171313017830946278

kd = calcKD(continued_fractions(n,e), ct, n)

Mr.D (12:10):

Okey, see you later ;)

Mr.D (19:30):

So can you help me?

Anonymous (19:31):

Yeah, we will have 10,000 falsified voters. Transfer 100000$ to my bank account: ctfzone{3177809746931830}

ctfzone{3177809746931830}

です。

RSA暗号を可能にしたEulerの定理 [単行本（ソフトカバー）]

田中 隆幸

東京図書出版

2017-02-03

e-Voting

CRYPTO

Organizers use this application for votes encryption. Each vote is a piece of data that looks like [‘ID’: x; ‘VOTE’: ‘ctfzone{xxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxx}’], where ID – user identifier, VOTE – elector identifier.

We were informed that one user managed to vote for one candidate several times. Unfortunately, we cannot decrypt the votes and organizers refuse to assist. Please, help to understand who has this guy voted for.

The security of this cryptosystem is based on the difficulty of finding discrete logarithms modulo a large prime. The system parameters consist of a prime P and an integer G, whose powers modulo P generate a large number of elements, as in Diffie-Hellman. Application has next functions:

Encrypt: encrypt(int(ptext, 16))

Decrypt: format(decrypt(int(ctext)), "x")

82.202.204.134:1331

$ nc 82.202.204.134 1331
Last vote: (82188365673110268294064121870080991705755725832546920062792095122208625769242 67718166941006068151871250413947876704800913199138538561553560012641121082386)

Options:

    [E]ncrypt message

    [D]ecrypt message

    [Q]uit

->

-> D
1 67718166941006068151871250413947876704800913199138538561553560012641121082386

5139dc16987b83af680aefa2af8d742d4593ebdfd5cbad6c7352738761e2f951

36739570011310345175058857194182124591023784382870723901126672546510051408209…(a)

2 67718166941006068151871250413947876704800913199138538561553560012641121082386

a273b82d30f7075ed015df455f1ae85a8b27d7bfab975ad8e6a4e70ec3c5f2a2

73479140022620690350117714388364249182047568765741447802253345093020102816418

3 67718166941006068151871250413947876704800913199138538561553560012641121082386

36ff256206ed2118a8166800eb5f3ec529fb64960a2da98198ceb2b2239bf80c

24875697832433900686586101358018082885574625713735199599830086245078003349516

4 67718166941006068151871250413947876704800913199138538561553560012641121082386

883901789f68a4c8102157a39aecb2f26f8f5075dff956ee0c212639857ef15d

61615267843744245861644958552200207476598410096605923500956758791588054757725

Last vote: (82188365673110268294064121870080991705755725832546920062792095122208625769242…(c) 67718166941006068151871250413947876704800913199138538561553560012641121082386)

a = 36739570011310345175058857194182124591023784382870723901126672546510051408209
b = 85343012201497134838590470224528290887496727434876972103549931394452150875111
c = 82188365673110268294064121870080991705755725832546920062792095122208625769242

d = a * c % b 

e = '%x' % d

print(e)

fc575129f3935d5b456ed55ef8173574

ctfzone{fc575129f3935d5b456ed55ef8173574}

暗号技術のすべて [単行本（ソフトカバー）]

IPUSIRON

翔泳社

2017-08-03