picoCTF2019 | Crypto Writeup

Cryptography Writeup

The numbers - Points 50
13 - Points 100
Easy1 - Points 100
caesar - Points: 100
Flags - Points: 200
Mr-Worldwide - Points: 200
Tapping - Points: 200
la cifra de - Points: 200
rsa-pop-quiz - Points: 200
waves over lambda - Points: 300
miniRSA - Points: 300

The numbers - Points 50: The numbers... what do they mean.


Associate numbers to alphabet letter

PICOCTF{THENUMBERSMASON}

13 - Points 100: Cryptography can be easy, do you know what ROT13 is? cvpbPGS{abg_gbb_onq_bs_n_ceboyrz}

Hint: This can be solved online if you don't want to do it by hand!


$ echo cvpbPGS{abg_gbb_onq_bs_n_ceboyrz} | tr 'A-Za-z' 'N-ZA-Mn-za-m'

picoCTF{not_too_bad_of_a_problem}

Easy1 - Points 100: The one time pad can be cryptographically secure, but not when you know the key. Can you solve this? We've given you the encrypted flag, key, and a table to help UFJKXQZQUNB with the key of SOLVECRYPTO. Can you use this table to solve it?.


    A B C D E F G H I J K L M N O P Q R S T U V W X Y Z
   +----------------------------------------------------
A | A B C D E F G H I J K L M N O P Q R S T U V W X Y Z
B | B C D E F G H I J K L M N O P Q R S T U V W X Y Z A
C | C D E F G H I J K L M N O P Q R S T U V W X Y Z A B
D | D E F G H I J K L M N O P Q R S T U V W X Y Z A B C
E | E F G H I J K L M N O P Q R S T U V W X Y Z A B C D
F | F G H I J K L M N O P Q R S T U V W X Y Z A B C D E
G | G H I J K L M N O P Q R S T U V W X Y Z A B C D E F
H | H I J K L M N O P Q R S T U V W X Y Z A B C D E F G
I | I J K L M N O P Q R S T U V W X Y Z A B C D E F G H
J | J K L M N O P Q R S T U V W X Y Z A B C D E F G H I
K | K L M N O P Q R S T U V W X Y Z A B C D E F G H I J
L | L M N O P Q R S T U V W X Y Z A B C D E F G H I J K
M | M N O P Q R S T U V W X Y Z A B C D E F G H I J K L
N | N O P Q R S T U V W X Y Z A B C D E F G H I J K L M
O | O P Q R S T U V W X Y Z A B C D E F G H I J K L M N
P | P Q R S T U V W X Y Z A B C D E F G H I J K L M N O
Q | Q R S T U V W X Y Z A B C D E F G H I J K L M N O P
R | R S T U V W X Y Z A B C D E F G H I J K L M N O P Q
S | S T U V W X Y Z A B C D E F G H I J K L M N O P Q R
T | T U V W X Y Z A B C D E F G H I J K L M N O P Q R S
U | U V W X Y Z A B C D E F G H I J K L M N O P Q R S T
V | V W X Y Z A B C D E F G H I J K L M N O P Q R S T U
W | W X Y Z A B C D E F G H I J K L M N O P Q R S T U V
X | X Y Z A B C D E F G H I J K L M N O P Q R S T U V W
Y | Y Z A B C D E F G H I J K L M N O P Q R S T U V W X
Z | Z A B C D E F G H I J K L M N O P Q R S T U V W X Y

Hint: Submit your answer in our competition's flag format. For example, if you answer was 'hello', you would submit 'picoCTF{HELLO}' as the flag. Please use all caps for the message.


It's a Vigenere code encryption

picoCTF{CRYPTOISFUN}

caesar - Points: 100: Decrypt this message (picoCTF{rgdhhxcviwtgjqxrdcdydkefyh}). You can find the ciphertext in /problems/caesar_6_238b8f4604d91ecb59cda5b4f0e66fc8 on the shell server.

Hint: caesar cipher tutorial

It's a Caesar cipher; below an implementation with python of Caesar Cipher Algorithm decodification


import string

# Encrypted message
message = 'rgdhhxcviwtgjqxrdcdydkefyh'
LETTERS = string.ascii_lowercase

for key in range(len(LETTERS)):
   translated = ''
   for symbol in message:
      if symbol in LETTERS:
         num = LETTERS.find(symbol)
         num = num - key
         if num < 0:
            num = num + len(LETTERS)
         translated = translated + LETTERS[num]
      else:
         translated = translated + symbol

   print('Hacking key #{}: {}'.format(key, translated))

picoCTF{crossingtherubiconojovpqjs}

Flags - Points: 200: What do the flags mean?

Hint: The flag is in the format PICOCTF{}


$ eog flag.png
# is the International Code of Signals, decode it and find the flag

PICOCTF{F1AG5AND5TUFF}

Mr-Worldwide - Points: 200: A musician left us a message. What's it mean?


picoCTF{(35.028309, 135.753082)(46.469391, 30.740883)(39.758949, -84.191605)(41.015137, 28.979530)(24.466667, 54.366669)(3.140853, 101.693207)_(9.005401, 38.763611)(-3.989038, -79.203560)(52.377956, 4.897070)(41.085651, -73.858467)(57.790001, -152.407227)(31.205753, 29.924526)}

Hint:


Decode the message by finding the first letter of each city at coordinates (x,y)

picoCTF{KODIAK_ALASKA}

Tapping - Points: 200: Theres tapping coming in from the wires. What's it saying nc 2019shell1.picoctf.com 32273.


.--. .. -.-. --- -.-. - ..-. { -- ----- .-. ... ...-- -.-. ----- -.. ...-- .---- ... ..-. ..- -. .---- -.... --... --... ..--- ..... --... ..--- ---.. --... }

Hint: What kind of encoding uses dashes and dots?

Hint: The flag is in the format PICOCTF{}


$ nc 2019shell1.picoctf.com 32273
# it's morse code
$ python
>>> s = picoctf{m0rs3c0d31sfun1677257287}
>>> s.upper()

PICOCTF{M0RS3C0D31SFUN1677257287}

la cifra de - Points: 200: I found this cipher in an old book. Can you figure out what it says? Connect with nc 2019shell1.picoctf.com 12254.


Encrypted message:

Ne iy nytkwpsznyg nth it mtsztcy vjzprj zfzjy rkhpibj nrkitt ltc tnnygy ysee itd tte cxjltk

Ifrosr tnj noawde uk siyyzre, yse Bnretèwp Cousex mls hjpn xjtnbjytki xatd eisjd

Iz bls lfwskqj azycihzeej yz Brftsk ip Volpnèxj ls oy hay tcimnyarqj dkxnrogpd os 1553 my Mnzvgs Mazytszf Merqlsu ny hox moup Wa inqrg ipl. Ynr. Gotgat Gltzndtg Gplrfdo

Ltc tnj tmvqpmkseaznzn uk ehox nivmpr g ylbrj ts ltcmki my yqtdosr tnj wocjc hgqq ol fy oxitngwj arusahje fuw ln guaaxjytrd catizm tzxbkw zf vqlckx hizm ceyupcz yz tnj fpvjc hgqqpohzCZK{m311a50_0x_a1rn3x3_h1ah3xf653pdkh}

Ehk ktryy herq-ooizxetypd jjdcxnatoty ol f aordllvmlbkytc inahkw socjgex, bls sfoe gwzuti 1467 my Rjzn Hfetoxea Gqmexyt.

Tnj Gimjyèrk Htpnjc iy ysexjqoxj dosjeisjd cgqwej yse Gqmexyt Doxn ox Fwbkwei Inahkw.

Tn 1508, Ptsatsps Zwttnjxiax tnbjytki ehk xz-cgqwej ylbaql rkhea (g rltxni ol xsilypd gqahggpty) ysaz bzuri wazjc bk f nroytcgq nosuznkse ol yse Bnretèwp Cousex.

Gplrfdo’y xpcuso butvlky lpvjlrki tn 1555 gx l cuseitzltoty ol yse lncsz. Yse rthex mllbjd ol yse gqahggpty fce tth snnqtki cemzwaxqj, bay ehk fwpnfmezx lnj yse osoed qptzjcs gwp mocpd hd xegsd ol f xnkrznoh vee usrgxp, wnnnh ify bk itfljcety hizm paim noxwpsvtydkse.

Hint: There are tools that make this easy.

Hint: Perhaps looking at history will help


$ nc 2019shell1.picoctf.com 12254
# simply try to break Vigenere without the key

picoCTF{b311a50_0r_v1gn3r3_c1ph3ra653edec}

rsa-pop-quiz - Points: 200: Class, take your seats! It's PRIME-time for a quiz... nc 2019shell1.picoctf.com 61751

Hint: RSA info


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): y
#### TIME TO SHOW ME WHAT YOU GOT! ###
n: 4636878989
Outstanding move!!!


#### NEW PROBLEM ####
p : 54269
n : 5051846941
##### PRODUCE THE FOLLOWING ####
q
IS THIS POSSIBLE and FEASIBLE? (Y/N): y
#### TIME TO SHOW ME WHAT YOU GOT! ###
q: 93089
Outstanding move!!!


#### NEW PROBLEM ####
e : 3
n : 12738162802910546503821920886905393316386362759567480839428456525224226
445173031635306683726182522494910808518920409019414034814409330094245825749
680913204566832337704700165993198897029795786969124232138869784626202501366
135975223827287812326250577148625360887698930625504334325804587329905617936
581116392784684334664204309771430814449606147221349888320403451637882447709
796221706470239625292297988766493746209684880843111138170600039888112404411
310974758532603998608057008811836384597579147244737606088756299939654265086
899096359070667266167754944587948695842171915048619846282873769413489072243
477764350071787327913
##### PRODUCE THE FOLLOWING ####
q
p
IS THIS POSSIBLE and FEASIBLE? (Y/N): n
Outstanding move!!!


#### NEW PROBLEM ####
q : 66347
p : 12611
##### PRODUCE THE FOLLOWING ####
totient(n)
IS THIS POSSIBLE and FEASIBLE? (Y/N): y
#### TIME TO SHOW ME WHAT YOU GOT! ###
totient(n): 836623060
Outstanding move!!!


#### NEW PROBLEM ####
plaintext : 635729417148931154719098761554457513358196788649948409135266140
641404444047520534288284123635766597343146249135508941371039227338020303879
3241564304774271529108729717
e : 3
n : 29129463609326322559521123136222078780585451208149138547799121083622333
250646678767769126248182207478527881025116332742616201890576280859777513414
460842754045651093593251726785499360828237897586278068419875517543013545369
871704159718105354690802726645710699029936754265654381929650494383622583174
075805797766685192325859982797796060391271817578087472948205626257717479858
369754502615173773514087437504532994142632207906501079835037052797306690891
600559321673928943158514646572885986881016569647357891598545880304236145548
059520898133142087545369179876065657214225826997676844000054327141666320553
082128424707948750331
##### PRODUCE THE FOLLOWING ####
ciphertext
IS THIS POSSIBLE and FEASIBLE? (Y/N): y
#### TIME TO SHOW ME WHAT YOU GOT! ###
ciphertext: 256931246631782714357241556582441991993437399854161372646318659
020994329843524306570818293602492485385337029697819837182169818816821461486
018802894936801257629375428544752970630870631166355711254848465862207765051
226282541748174535990314552471546936536330397892907207943448897073772015986
097770443616540466471245438117157152783246654401668267323136450122287983612
851171545784168132230208726238881861407976917850248110805724300421712827401
063963117423718797887144760360749619552577176382615108244813
Outstanding move!!!


#### NEW PROBLEM ####
ciphertext : 10752401345107934853994451075614360420392571726218503379932844
501179276054552894499371978339254216342863717232351225262456711111066616866
474311520379151098570994236660962643699588778167465127223356630381497967750
710116858773937569900973458898548236970263449954489150922844019461537633957
3685285125730286623323
e : 3
n : 27566996291508213932419371385141522859343226560050921196294761870500846
140132385080994630946107675330189606021165260590147068785820203600882092467
797813519434652632126061353583124063944373336654246386074125394368479677295
167494332556053947231141336142392086767742035970752738056297057898704112912
616565299451359791548536846025854378347423520104947907334451056339439706623
069503088916316369813499705073573777577169392401411708920615574908593784282
546154486446779246790294398198854547069593987224578333683144886242572837465
834139561122101527973799583927411936200068176539747586449939559180772690007
261562703222558103359
##### PRODUCE THE FOLLOWING ####
plaintext
IS THIS POSSIBLE and FEASIBLE? (Y/N): n
Outstanding move!!!


#### NEW PROBLEM ####
q : 92092076805892533739724722602668675840671093008520241548191914215399824
020372076186460768206814914423802230398410980218741906960527104568970225804
374404612617736579286959865287226538692911376507934256844456333236362669879
347073756238894784951597211105734179388300051579994253565459304743059533646
753003894559
p : 97846775312392801037224396977012615848433199640105786119757047098757998
273009741128821931277074555731813289423891389911801250326299324018557072727
051765547115514791337578758859803890173153277252326496062476389498019821358
465433398338364421624871010292162533041884897182597065662521825095949253625
730631876637
e : 65537
##### PRODUCE THE FOLLOWING ####
d
IS THIS POSSIBLE and FEASIBLE? (Y/N): y
#### TIME TO SHOW ME WHAT YOU GOT! ###
d: 140504626950320746914079154840363953312741641621421069497208507917178758
046377682042596589817427287048601573951612578618282163700660074214068255232
164550374328067083981907874909273011054988189127131739645015802168825398976
714557872345825276946554550414213966347674747922592393319242140546441457478
627296374165622394175008405122861157670860934678710108875906272438987416069
300878333460590314252882455922351520397870796979508750667889400662829674307
988624434946913183122575792684484355489763878614603686957265320473565084318
672273273688891878937905405012220525316570508553874365125840039058097104314
4644984654914856729
Outstanding move!!!


#### NEW PROBLEM ####
p : 15314304227252786879841261241720443415693514687428299094238669402046286
191806868456128176357703470660060838769914807101519472553339412606982685718
242866042781827737872497755436591023152482725816090449377474874908847732820
481217193598708871526112732191184909220707065327217607250993324597893545554
2420691737433
ciphertext : 92761828917525309012199274120731436719488754821388835429384012
048677761716051275721340364449531377907450038881894439764755781201444294907
057846495077866867882173213448858448276476545129493546619736116648727833935
019921124648254413309614576287582240116587850829959456121950731916019522383
613158203733736066435214634663760952363717789849428911239361917967200979005
935994475285832578061965517246763801351106932283309344181477593879907543685
250686858615479779930851493591627548906744878230807505796011008547950312845
338648262552073003506795534865059618373490427788510105695824586296386485894
42067576234798724906377157351
e : 65537
n : 23952937352643527451379227516428377705004894508566304313177880191662177
061878993798938496818120987817049538365206671401938265663712351239785237507
341311858383628932183083145614696585411921662992078376103990806989257289472
590902167457302888198293135333083734504191910953238278860923153746261500759
411620299864395158783509535039259714359526738924736952759753503357614939203
434092075676169179112452620687731670534906069845965633455748606649062394293
289967059348143206600765820021392608270528856238306849191113241355842396325
210132358046616312901337987464473799040762271876389031455051640937681745409
057246190498795697239
##### PRODUCE THE FOLLOWING ####
plaintext
IS THIS POSSIBLE and FEASIBLE? (Y/N): yes
#### TIME TO SHOW ME WHAT YOU GOT! ###
plaintext: 1431166394270967486712220821490197065049678815123952097162341171
2977119642137567031494784893
Outstanding move!!!


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


$ python3
>>> hex(143116639427096748671222082149019706504967881512395209716234117129
77119642137567031494784893)
>>> bytearray.fromhex("7069636f4354467b7741385f74683474245f696c6c336147616
c2e2e6f31383238643335377d").decode()

Below the python script used to solve this challenge


#! /usr/bin/env python3

# -------------------------------------------------------------------
# Choice Number 1
# -------------------------------------------------------------------
def calculate_n(p,q):
    n = p * q
    print("\n\tn: {}".format(n))
    return n

# -------------------------------------------------------------------
# Choice Number 2
# -------------------------------------------------------------------
def calculate_q(p,n):
    q = n/p
    print("\n\tq: {}".format(q))
    return q

# -------------------------------------------------------------------
# Choice Number 3
# -------------------------------------------------------------------
def calculate_phi_n(p,q):
    phi_n = (p-1) * (q-1)
    print("\n\tPhi_n: {}".format(phi_n))
    return phi_n

# -------------------------------------------------------------------
# Choice Number 4
# -------------------------------------------------------------------
def calculate_c(m,n,e):
    c = pow(m,e,n)
    print("\n\tc: {}".format(c))
    return c

# -------------------------------------------------------------------
# Choice Number 5
# -------------------------------------------------------------------

def calculate_d(p,q,e):
    phi = (p-1) * (q-1)
    d = modinv(e, phi)
    print("\n\td: {}".format(d))
    return d

# Euclid's Extended GCD algorithm.
def egcd(a, b):
    if a == 0:
        return b, 0, 1
    else:
        g, y, x = egcd(b % a, a)

    return g, x - (b // a) * y, y


# Modular inverse using the e-GCD algorithm.
def modinv(a, m):
    g, x, y = egcd(a, m)
    if g != 1:
        raise Exception('Modular inverse does not exist')
    else:
        return x % m

# -------------------------------------------------------------------
# Choice Number 6
# -------------------------------------------------------------------

def calculate_m(e,n,p,c):
    q = int(n//p)
    d = calculate_d(p,q,e)
    m = pow(c,d,n)
    print("\n\tm: {}".format(m))

def menu():
    choice ='0'
    while choice !='-1':
        print("Main Choice: Choose 1 of 5 choices")
        print("Choose 1 for n given p,q")
        print("Choose 2 for q given p,n")
        print("Choose 3 for phi(n) given p,q")
        print("Choose 4 for cyphertext(c) given messsage(m),e,n")
        print("Choose 5 for d given q,p,e")
        print("Choose 6 for m given e,n,p")

        print("Choose -1 to exit")

        choice = input ("Please make a choice: ")
        print("\n")

        if choice == "1":
            p = int(input("p: "))
            q = int(input("q: "))
            calculate_n(p,q)
            print('\n')

        elif choice == "2":
            p = int(input("p: "))
            n = int(input("n: "))
            calculate_q(p,n)
            print('\n')

        elif choice == "3":
            p = int(input("p: "))
            q = int(input("q: "))
            calculate_phi_n(p,q)
            print('\n')

        elif choice == "4":
            m = int(input("m: "))
            n = int(input("n: "))
            e = int(input("e: "))
            calculate_c(m,n,e)
            print('\n')

        elif choice == "5":
            p = int(input("p: "))
            q = int(input("q: "))
            e = int(input("e: "))
            calculate_d(p,q,e)
            print('\n')

        elif choice == "6":
            e = int(input("e: "))
            n = int(input("n: "))
            p = int(input("p: "))
            c = int(input("c: "))
            calculate_m(e,n,p,c)
            print('\n')

        elif choice == "-1":
            print('Exiting...\n')

        else:
            print("I don't understand your choice.")

if __name__ == '__main__':

    menu()

picoCTF{wA8_th4t$_ill3aGal..o1828d357}

waves over lambda - Points: 300: We made alot of substitutions to encrypt this. Can you decrypt it? Connect with nc 2019shell1.picoctf.com 49935.


-------------------------------------------------------------------------------
mirufzjb ptft hb ciyf lszu - lftwytrmc_hb_m_ivtf_szoqkz_lkhhhfyqfz
-------------------------------------------------------------------------------
dt dtft rij oymp oift jpzr z wyzfjtf il zr piyf iyj il iyf bphg jhss dt bzd ptf bhrn, zrk jptr h yrktfbjiik lif jpt lhfbj jhot dpzj dzb otzrj qc z bphg liyrktfhru hr jpt btz.  h oybj zmnridstkut h pzk pzfksc tctb ji siin yg dptr jpt btzotr jisk ot bpt dzb bhrnhru; lif lfio jpt oiotrj jpzj jptc fzjptf gyj ot hrji jpt qizj jpzr jpzj h ohupj qt bzhk ji ui hr, oc ptzfj dzb, zb hj dtft, ktzk dhjphr ot, gzfjsc dhjp lfhupj, gzfjsc dhjp piffif il ohrk, zrk jpt jpiyupjb il dpzj dzb ctj qtlift ot.

Hint: Flag is not in the usual flag format


$ nc 2019shell1.picoctf.com 49935
# it's mono-alphabetic substitution cipher
# https://www.dcode.fr/monoalphabetic-substitution

picoCTF{frequency_is_c_over_lambda_fdiiirubra}

miniRSA - Points: 300: Lets decrypt this: ciphertext? Something seems a bit small


N: 293319224997949857827359760455911649366830593805589503865601601057403432
015133699390063075311659227089496191626986236753490304308595478257089947083
218037053094594380993404277705800644009114318566569019827899482853099561118
486869061526644733509404865074517712234358352601689712100874708944484607455
939568405865305279158025414500929465746948095848808966013175197944428629774
711293197813131618420565017150405559640118995890028637308686795271844207890
105514750678629077390549661831206214072463985180989811064312192076978702934
121764404829001835504673751902398984552011708314104604838294486034773613058
38743852756938687673
e: 3
ciphertext: 220531641393113403107460374692824779903015522125251987264961368
640888479853032113918319411438067576098067528821350949448892814989037835035
824553674597025316228353496854530017839690022613145424062554002629647343489
5830304509610598192929125

Hint: How could having too small an e affect the security of this 2048 bit key?

Hint: Make sure you dont lose precision, the numbers are pretty big (besides the e value)

As the difference between n and e suggest, to break this challenge a "low public exponent attack" is needed. This kind of attack is successful only if m, the plaintex, is short too.


import gmpy2

c = int(input("c: "))
n = int(input("n: "))
e = int(input("e: "))

gs = gmpy2.mpz(c)
gm = gmpy2.mpz(n)
ge = gmpy2.mpz(e)

root, exact = gmpy2.iroot(gs, ge)

if(exact):
  print(bytes.fromhex(hex(int(root))[2:]))

picoCTF{n33d_a_lArg3r_e_2f75924d}

Cryptography Writeup

Table of Contents