Skip to content

Latest commit

 

History

History
194 lines (154 loc) · 13.2 KB

rsaPopQuiz.md

File metadata and controls

194 lines (154 loc) · 13.2 KB

PicoCTF 2019 - rsa-pop-quiz

Author: PinkNoize

Cryptography - 200

Class, take your seats! It's PRIME-time for a quiz... nc 2019shell1.picoctf.com 49989

Writeup

This challenge gives us a netcat command to run which quizzes us on our knowledge of RSA. I recommend reading and using the RSA Algorithm Wiki Page linked in the hint as a cheatsheet.

Upon connecting the first question we get asked is,

Good morning class! It's me Ms. Adleman-Shamir-Rivest
Today we will be taking a pop quiz, so I hope you studied. Cramming just will not do!
You will need to tell me if each example is possible, given your extensive crypto knowledge.
Inputs and outputs are in decimal. No hex here!
#### NEW PROBLEM ####
q : 60413
p : 76753
##### PRODUCE THE FOLLOWING ####
n
IS THIS POSSIBLE and FEASIBLE? (Y/N)

As n = p*q, this is feasible and we could do this calculation by hand if we wanted to. I will be using python for all calculations.

>>> 60413*76753
4636878989

We then get asked

#### NEW PROBLEM ####
p : 54269
n : 5051846941
##### PRODUCE THE FOLLOWING ####
q
IS THIS POSSIBLE and FEASIBLE? (Y/N):

This uses the same equation and is feasible. We can solve this by rearranging the equation above, q = n/p.

>>> 5051846941/54269
93089.0

The next question is

#### NEW PROBLEM ####
e : 3
n : 12738162802910546503821920886905393316386362759567480839428456525224226445173031635306683726182522494910808518920409019414034814409330094245825749680913204566832337704700165993198897029795786969124232138869784626202501366135975223827287812326250577148625360887698930625504334325804587329905617936581116392784684334664204309771430814449606147221349888320403451637882447709796221706470239625292297988766493746209684880843111138170600039888112404411310974758532603998608057008811836384597579147244737606088756299939654265086899096359070667266167754944587948695842171915048619846282873769413489072243477764350071787327913
##### PRODUCE THE FOLLOWING ####
q
p
IS THIS POSSIBLE and FEASIBLE? (Y/N):

This question is essentially asking us to factor the two primes that make up n. That is a hard problem and part of what secures RSA. This is not feasible.

We are then asked

#### NEW PROBLEM ####
q : 66347
p : 12611
##### PRODUCE THE FOLLOWING ####
totient(n)
IS THIS POSSIBLE and FEASIBLE? (Y/N):

As defined by the Euler's totient function wikipedia page, "the totient of a positive integer is the number of positive integers smaller than n which are coprime to n (they share no factors except 1)."

We can define a function in python to calculate the totient.

import math
def totient(n):
    t = 0
    # iterate over all smaller positive integers
    for i in range(n):
        # check if coprime
        if math.gcd(i,n) == 1:
            t += 1
    return t

While the code above is correct, if you try it you will see that this takes forever. We can use the equation listed on the RSA algorithm page, Φ(n) = (p-1)(q-1). This equation exploits that p and q are prime along with n's construction.

>>> (66347-1)*(12611-1)
836623060

The next question is

#### NEW PROBLEM ####
plaintext : 6357294171489311547190987615544575133581967886499484091352661406414044440475205342882841236357665973431462491355089413710392273380203038793241564304774271529108729717
e : 3
n : 29129463609326322559521123136222078780585451208149138547799121083622333250646678767769126248182207478527881025116332742616201890576280859777513414460842754045651093593251726785499360828237897586278068419875517543013545369871704159718105354690802726645710699029936754265654381929650494383622583174075805797766685192325859982797796060391271817578087472948205626257717479858369754502615173773514087437504532994142632207906501079835037052797306690891600559321673928943158514646572885986881016569647357891598545880304236145548059520898133142087545369179876065657214225826997676844000054327141666320553082128424707948750331
##### PRODUCE THE FOLLOWING ####
ciphertext
IS THIS POSSIBLE and FEASIBLE? (Y/N):

As the encryption equation is c = m^e mod n and we have all the components, this is feasible.

>>> m = 6357294171489311547190987615544575133581967886499484091352661406414044440475205342882841236357665973431462491355089413710392273380203038793241564304774271529108729717
>>> e = 3
>>> n = 29129463609326322559521123136222078780585451208149138547799121083622333250646678767769126248182207478527881025116332742616201890576280859777513414460842754045651093593251726785499360828237897586278068419875517543013545369871704159718105354690802726645710699029936754265654381929650494383622583174075805797766685192325859982797796060391271817578087472948205626257717479858369754502615173773514087437504532994142632207906501079835037052797306690891600559321673928943158514646572885986881016569647357891598545880304236145548059520898133142087545369179876065657214225826997676844000054327141666320553082128424707948750331
>>> pow(m, e, n)
256931246631782714357241556582441991993437399854161372646318659020994329843524306570818293602492485385337029697819837182169818816821461486018802894936801257629375428544752970630870631166355711254848465862207765051226282541748174535990314552471546936536330397892907207943448897073772015986097770443616540466471245438117157152783246654401668267323136450122287983612851171545784168132230208726238881861407976917850248110805724300421712827401063963117423718797887144760360749619552577176382615108244813

NOTE: This equation is known as modular exponentiation. If you try to compute this by calculating m^e first then doing the mod after (m**e % n), it will take a long time when a large e is used. pow() with 3 arguments uses an efficient algorithm.

We are then asked

#### NEW PROBLEM ####
ciphertext : 107524013451079348539944510756143604203925717262185033799328445011792760545528944993719783392542163428637172323512252624567111110666168664743115203791510985709942366609626436995887781674651272233566303814979677507101168587739375699009734588985482369702634499544891509228440194615376339573685285125730286623323
e : 3
n : 27566996291508213932419371385141522859343226560050921196294761870500846140132385080994630946107675330189606021165260590147068785820203600882092467797813519434652632126061353583124063944373336654246386074125394368479677295167494332556053947231141336142392086767742035970752738056297057898704112912616565299451359791548536846025854378347423520104947907334451056339439706623069503088916316369813499705073573777577169392401411708920615574908593784282546154486446779246790294398198854547069593987224578333683144886242572837465834139561122101527973799583927411936200068176539747586449939559180772690007261562703222558103359
##### PRODUCE THE FOLLOWING ####
plaintext
IS THIS POSSIBLE and FEASIBLE? (Y/N):

This question asks us to decrypt the ciphertext given the public key (e) and the public modulus(n). If we could do this, RSA would be useless so it is not feasible.

#### NEW PROBLEM ####
q : 92092076805892533739724722602668675840671093008520241548191914215399824020372076186460768206814914423802230398410980218741906960527104568970225804374404612617736579286959865287226538692911376507934256844456333236362669879347073756238894784951597211105734179388300051579994253565459304743059533646753003894559
p : 97846775312392801037224396977012615848433199640105786119757047098757998273009741128821931277074555731813289423891389911801250326299324018557072727051765547115514791337578758859803890173153277252326496062476389498019821358465433398338364421624871010292162533041884897182597065662521825095949253625730631876637
e : 65537
##### PRODUCE THE FOLLOWING ####
d
IS THIS POSSIBLE and FEASIBLE? (Y/N):

This question asks us to calculate the private key given, p,q and e. As described in the RSA algorithm wiki page, d is calculated by d = (1 + x*Φ(n))/e where x and d are integers. d can also be computed of the modular inverse of e and Φ(n).

>>> p = 97846775312392801037224396977012615848433199640105786119757047098757998273009741128821931277074555731813289423891389911801250326299324018557072727051765547115514791337578758859803890173153277252326496062476389498019821358465433398338364421624871010292162533041884897182597065662521825095949253625730631876637
>>> q = 92092076805892533739724722602668675840671093008520241548191914215399824020372076186460768206814914423802230398410980218741906960527104568970225804374404612617736579286959865287226538692911376507934256844456333236362669879347073756238894784951597211105734179388300051579994253565459304743059533646753003894559
>>> e = 65537
>>> pow(e, -1, (p-1)*(q-1))
1405046269503207469140791548403639533127416416214210694972085079171787580463776820425965898174272870486015739516125786182821637006600742140682552321645503743280670839819078749092730110549881891271317396450158021688253989767145578723458252769465545504142139663476747479225923933192421405464414574786272963741656223941750084051228611576708609346787101088759062724389874160693008783334605903142528824559223515203978707969795087506678894006628296743079886244349469131831225757926844843554897638786146036869572653204735650843186722732736888918789379054050122205253165705085538743651258400390580971043144644984654914856729

The next question is

#### NEW PROBLEM ####
p : 153143042272527868798412612417204434156935146874282990942386694020462861918068684561281763577034706600608387699148071015194725533394126069826857182428660427818277378724977554365910231524827258160904493774748749088477328204812171935987088715261127321911849092207070653272176072509933245978935455542420691737433
ciphertext : 17712948302053968160337608808023765353713891487724504165710075800666176704275900270871131114252105275962867934935572601922131269231577652839874752278037120009042079114201440532529424282349775046830004126930931418790562922816147664822871476098418888441696782597264107603520215924140671864491508516555630119132820414262583115708142593728022851982531082194761937261873838830778405312620786370902097963783652483624611685252621820304116460797923537545175795133241570733730324869356742756474956593641308168807758853188030625975084213572477077655289967561799083034525042713829515144782123152608246868892673838596163063470464
e : 65537
n : 23952937352643527451379227516428377705004894508566304313177880191662177061878993798938496818120987817049538365206671401938265663712351239785237507341311858383628932183083145614696585411921662992078376103990806989257289472590902167457302888198293135333083734504191910953238278860923153746261500759411620299864395158783509535039259714359526738924736952759753503357614939203434092075676169179112452620687731670534906069845965633455748606649062394293289967059348143206600765820021392608270528856238306849191113241355842396325210132358046616312901337987464473799040762271876389031455051640937681745409057246190498795697239
##### PRODUCE THE FOLLOWING ####
plaintext
IS THIS POSSIBLE and FEASIBLE? (Y/N):

The decryption equation is m = c^d mod n. We have c and n but not d. We can calculate d using p, n and e so it is feasible.

>>> c = 17712948302053968160337608808023765353713891487724504165710075800666176704275900270871131114252105275962867934935572601922131269231577652839874752278037120009042079114201440532529424282349775046830004126930931418790562922816147664822871476098418888441696782597264107603520215924140671864491508516555630119132820414262583115708142593728022851982531082194761937261873838830778405312620786370902097963783652483624611685252621820304116460797923537545175795133241570733730324869356742756474956593641308168807758853188030625975084213572477077655289967561799083034525042713829515144782123152608246868892673838596163063470464
>>> n = 23952937352643527451379227516428377705004894508566304313177880191662177061878993798938496818120987817049538365206671401938265663712351239785237507341311858383628932183083145614696585411921662992078376103990806989257289472590902167457302888198293135333083734504191910953238278860923153746261500759411620299864395158783509535039259714359526738924736952759753503357614939203434092075676169179112452620687731670534906069845965633455748606649062394293289967059348143206600765820021392608270528856238306849191113241355842396325210132358046616312901337987464473799040762271876389031455051640937681745409057246190498795697239
>>> e = 65537
>>> p = 153143042272527868798412612417204434156935146874282990942386694020462861918068684561281763577034706600608387699148071015194725533394126069826857182428660427818277378724977554365910231524827258160904493774748749088477328204812171935987088715261127321911849092207070653272176072509933245978935455542420691737433
>>> q = n//p # integer division to avoid float error
>>> d = pow(e, -1, (p-1)*(q-1))
>>> pow(c, d, n)
14311663942709674867122208214901970650496788151239520971623411712977120545970596944152836477

After submitting the last answer we get instructions to get the flag.

If you convert the last plaintext to a hex number, then ascii, you'll find what you need! ;)

>>> int.to_bytes(14311663942709674867122208214901970650496788151239520971623411712977120545970596944152836477, 40, 'big')
b'\x00\x00picoCTF{wA8_th4t$_ill3aGal..ob7f0bd39}'

As shown above the flag is picoCTF{wA8_th4t$_ill3aGal..ob7f0bd39}.