picoCTF 2018 Write-up [Cryptography]
- まえがき
- Cryptography
- Crypto Warmup 1 - Points: 75
- Crypto Warmup 2 - Points: 75
- HEEEEEEERE'S Johnny! - Points: 100
- caesar cipher 1 - Points: 150
- hertz - Points: 150
- blaise's cipher - Points: 200
- hertz 2 - Points: 200
- Safe RSA - Points: 250
- caesar cipher 2 - Points: 250
- rsa-madlibs - Points: 250
- Super Safe RSA - Points: 350
- Super Safe RSA 2 - Points: 425
- Super Safe RSA 3 - Points: 600
- まとめ
まえがき
前回の続きです．
今回はCryptographyのWrite-upを書こうと思います．
Cryptography
Crypto Warmup 1 - Points: 75
Crpyto can often be done by hand, here's a message you got from a friend,
llkjmlmpadkkcwith the key ofthisisalilkey. 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
アプローチ：ヴィジュネル暗号
https://en.wikipedia.org/wiki/Vigen%C3%A8re_cipher
tableの最上段が平文(P)，左段が鍵(K)になります．
text: llkjmlmpadkkc
key: thisisalilkey
-> SECRETMESSAGE
picoCTF{SECRETMESSAGE}
暗号文をCとしたときに
となることを利用してスクリプトを書いたほうが速いです．
Crypto Warmup 2 - Points: 75
Cryptography doesn't have to be complicated, have you ever heard of something called rot13? cvpbPGS{guvf_vf_pelcgb!}
アプローチ：rot13
picoCTF{this_is_crypto!}
HEEEEEEERE'S Johnny! - Points: 100
Okay, so we found some important looking files on a linux computer. Maybe they can be used to get a password to the process. Connect with nc
2018shell1.picoctf.com 42165. Files can be found here: passwd shadow.
passwd
root:x:0:0:root:/root:/bin/bash
shadow
root:$6$q7xpw/2.$la4KiUz87ohdszbOVoIopy2VTwm/5jEXvWSdWynh0CnP5T.MnJfVNCzp3IfJMHUNuBhr1ewcYd8PyeKHqHQoe.:17770:0:99999:7:::
アプローチ：John the Ripper
ncするとユーザ名とパスワードの入力を求められるのでどうやらpasswdとshadowからユーザ名とパスワードを推測しなければいけないようです．
/etc/passwdと/etc/shadowについては以下を参照するといいと思います．
www.server-memo.net
shadowファイル解読のためにJohn the Ripperを使います．
https://www.openwall.com/john/
> john --show shadow root:kissme:17770:0:99999:7::: 1 password hash cracked, 0 left
root,kissmeでログイン
> nc 2018shell1.picoctf.com 42165
Username: root
Password: kissme
picoCTF{J0hn_1$_R1pp3d_5f9a67aa}
picoCTF{J0hn_1$_R1pp3d_5f9a67aa}
caesar cipher 1 - Points: 150
This is one of the older ciphers in the books, can you decrypt the message? You can find the ciphertext in /problems/caesar-cipher-1_3_160978e2a142244574bd048623dba1ed on the shell server.
grpqxdllaliazxbpxozfmebotlvlicmr
アプローチ：rot
rot13.com でrot3
picoCTF{justagoodoldcaesarcipherwoyolfpu}
hertz - Points: 150
Here's another simple cipher for you where we made a bunch of substitutions. Can you decrypt it? Connect with nc
2018shell1.picoctf.com 18581.
アプローチ：換字式暗号
ncすると
------------------------------------------------------------------------------- crjgeqof nzez xf urve kpqg - fvtfoxovoxrj_cxdnzef_qez_frphqtpz_kgjhhgjimf ------------------------------------------------------------------------------- xj q hxppqgz rk pq mqjcnq, onz jqmz rk anxcn x nqhz jr izfxez or cqpp or mxji, onzez pxhzi jro prjg fxjcz rjz rk onrfz gzjopzmzj onqo szzd q pqjcz xj onz pqjcz-eqcs, qj rpi tvcspze, q pzqj nqcs, qji q gezunrvji kre crvefxjg. qj rppq rk eqonze mrez tzzk onqj mvoorj, q fqpqi rj mrfo jxgnof, fceqdf rj fqoveiquf, pzjoxpf rj kexiquf, qji q dxgzrj re fr zwoeq rj fvjiquf, mqiz qaqu axon onezz-bvqeozef rk nxf xjcrmz. onz ezfo rk xo azjo xj q irvtpzo rk kxjz cpron qji hzphzo tezzcnzf qji fnrzf or mqocn kre nrpxiquf, anxpz rj azzs-iquf nz mqiz q teqhz kxgvez xj nxf tzfo nrmzfdvj. nz nqi xj nxf nrvfz q nrvfzszzdze dqfo kreou, q jxzcz vjize oazjou, qji q pqi kre onz kxzpi qji mqeszo-dpqcz, anr vfzi or fqiipz onz nqcs qf azpp qf nqjipz onz txpp-nrrs. onz qgz rk onxf gzjopzmqj rk rvef aqf treizexjg rj kxkou; nz aqf rk q nqeiu nqtxo, fdqez, gqvjo-kzqovezi, q hzeu zqepu exfze qji q gezqo fdreofmqj. onzu axpp nqhz xo nxf fvejqmz aqf bvxwqiq re bvzfqiq (kre nzez onzez xf frmz ixkkzezjcz rk rdxjxrj qmrjg onz qvonref anr aexoz rj onz fvtlzco), qponrvgn kerm ezqfrjqtpz crjlzcovezf xo fzzmf dpqxj onqo nz aqf cqppzi bvzwqjq. onxf, nrazhze, xf rk tvo pxoopz xmdreoqjcz or rve oqpz; xo axpp tz zjrvgn jro or foequ q nqxe'f tezqion kerm onz oevon xj onz ozppxjg rk xo. urv mvfo sjra, onzj, onqo onz qtrhz-jqmzi gzjopzmqj anzjzhze nz aqf qo pzxfvez (anxcn aqf mrfopu qpp onz uzqe ervji) gqhz nxmfzpk vd or ezqixjg trrsf rk cnxhqpeu axon fvcn qeirve qji qhxixou onqo nz qpmrfo zjoxezpu jzgpzcozi onz dvefvxo rk nxf kxzpi-fdreof, qji zhzj onz mqjqgzmzjo rk nxf derdzeou; qji or fvcn q dxocn ixi nxf zqgzejzff qji xjkqovqoxrj gr onqo nz frpi mqju qj qcez rk oxppqgzpqji or tvu trrsf rk cnxhqpeu or ezqi, qji tervgno nrmz qf mqju rk onzm qf nz crvpi gzo. tvo rk qpp onzez azez jrjz nz pxszi fr azpp qf onrfz rk onz kqmrvf kzpxcxqjr iz fxphq'f crmdrfxoxrj, kre onzxe pvcxixou rk foupz qji crmdpxcqozi crjczxof azez qf dzqepf xj nxf fxgno, dqeoxcvpqepu anzj xj nxf ezqixjg nz cqmz vdrj crveofnxdf qji cqeozpf, anzez nz rkozj krvji dqffqgzf pxsz "onz ezqfrj rk onz vjezqfrj axon anxcn mu ezqfrj xf qkkpxcozi fr azqszjf mu ezqfrj onqo axon ezqfrj x mvemve qo urve tzqvou;" re qgqxj, "onz nxgn nzqhzjf, onqo rk urve ixhxjxou ixhxjzpu kreoxku urv axon onz foqef, ezjize urv izfzehxjg rk onz izfzeo urve gezqojzff izfzehzf." rhze crjczxof rk onxf freo onz drre gzjopzmqj prfo nxf axof, qji vfzi or pxz qaqsz foexhxjg or vjizefoqji onzm qji arem onz mzqjxjg rvo rk onzm; anqo qexforopz nxmfzpk crvpi jro nqhz mqiz rvo re zwoeqcozi nqi nz crmz or pxkz qgqxj kre onqo fdzcxqp dvedrfz. nz aqf jro qo qpp zqfu qtrvo onz arvjif anxcn irj tzpxqjxf gqhz qji orrs, tzcqvfz xo fzzmzi or nxm onqo, gezqo qf azez onz fvegzrjf anr nqi cvezi nxm, nz mvfo nqhz nqi nxf kqcz qji triu crhzezi qpp rhze axon fzqmf qji fcqef. nz crmmzjizi, nrazhze, onz qvonre'f aqu rk zjixjg nxf trrs axon onz dermxfz rk onqo xjozemxjqtpz qihzjovez, qji mqju q oxmz aqf nz ozmdozi or oqsz vd nxf dzj qji kxjxfn xo derdzepu qf xf onzez derdrfzi, anxcn jr irvto nz arvpi nqhz irjz, qji mqiz q fvcczffkvp dxzcz rk ares rk xo orr, nqi jro gezqoze qji mrez qtfretxjg onrvgnof dezhzjozi nxm.
が降ってきます．
おそらく換字式暗号なので文字の出現確率を見ながら適当に変換していきます．
変換ルールはこれです．
q -> A g -> G p -> L k -> F e -> R z -> E n -> H r -> O o -> T j -> N m -> M i -> D x -> I f -> S v -> U a -> W c -> C u -> Y t -> B d -> P s -> K h -> V w -> X l -> J b -> Q
最終的な文字列は以下のようになります．
------------------------------------------------------------------------------- CONGRATS HERE IS YOUR FLAG - SUBSTITUTION_CIPHERS_ARE_SOLVABLE_FGNVVGNDMS ------------------------------------------------------------------------------- IN A VILLAGE OF LA MANCHA, THE NAME OF WHICH I HAVE NO DESIRE TO CALL TO MIND, THERE LIVED NOT LONG SINCE ONE OF THOSE GENTLEMEN THAT KEEP A LANCE IN THE LANCE-RACK, AN OLD BUCKLER, A LEAN HACK, AND A GREYHOUND FOR COURSING. AN OLLA OF RATHER MORE BEEF THAN MUTTON, A SALAD ON MOST NIGHTS, SCRAPS ON SATURDAYS, LENTILS ON FRIDAYS, AND A PIGEON OR SO EXTRA ON SUNDAYS, MADE AWAY WITH THREE-QUARTERS OF HIS INCOME. THE REST OF IT WENT IN A DOUBLET OF FINE CLOTH AND VELVET BREECHES AND SHOES TO MATCH FOR HOLIDAYS, WHILE ON WEEK-DAYS HE MADE A BRAVE FIGURE IN HIS BEST HOMESPUN. HE HAD IN HIS HOUSE A HOUSEKEEPER PAST FORTY, A NIECE UNDER TWENTY, AND A LAD FOR THE FIELD AND MARKET-PLACE, WHO USED TO SADDLE THE HACK AS WELL AS HANDLE THE BILL-HOOK. THE AGE OF THIS GENTLEMAN OF OURS WAS BORDERING ON FIFTY; HE WAS OF A HARDY HABIT, SPARE, GAUNT-FEATURED, A VERY EARLY RISER AND A GREAT SPORTSMAN. THEY WILL HAVE IT HIS SURNAME WAS QUIXADA OR QUESADA (FOR HERE THERE IS SOME DIFFERENCE OF OPINION AMONG THE AUTHORS WHO WRITE ON THE SUBJECT), ALTHOUGH FROM REASONABLE CONJECTURES IT SEEMS PLAIN THAT HE WAS CALLED UEXANA. THIS, HOWEVER, IS OF BUT LITTLE IMPORTANCE TO OUR TALE; IT WILL BE ENOUGH NOT TO STRAY A HAIR'S BREADTH FROM THE TRUTH IN THE TELLING OF IT. YOU MUST KNOW, THEN, THAT THE ABOVE-NAMED GENTLEMAN WHENEVER HE WAS AT LEISURE (WHICH WAS MOSTLY ALL THE YEAR ROUND) GAVE HIMSELF UP TO READING BOOKS OF CHIVALRY WITH SUCH ARDOUR AND AVIDITY THAT HE ALMOST ENTIRELY NEGLECTED THE PURSUIT OF HIS FIELD-SPORTS, AND EVEN THE MANAGEMENT OF HIS PROPERTY; AND TO SUCH A PITCH DID HIS EAGERNESS AND INFATUATION GO THAT HE SOLD MANY AN ACRE OF TILLAGELAND TO BUY BOOKS OF CHIVALRY TO READ, AND BROUGHT HOME AS MANY OF THEM AS HE COULD GET. BUT OF ALL THERE WERE NONE HE LIKED SO WELL AS THOSE OF THE FAMOUS FELICIANO DE SILVA'S COMPOSITION, FOR THEIR LUCIDITY OF STYLE AND COMPLICATED CONCEITS WERE AS PEARLS IN HIS SIGHT, PARTICULARLY WHEN IN HIS READING HE CAME UPON COURTSHIPS AND CARTELS, WHERE HE OFTEN FOUND PASSAGES LIKE "THE REASON OF THE UNREASON WITH WHICH MY REASON IS AFFLICTED SO WEAKENS MY REASON THAT WITH REASON I MURMUR AT YOUR BEAUTY;" OR AGAIN, "THE HIGH HEAVENS, THAT OF YOUR DIVINITY DIVINELY FORTIFY YOU WITH THE STARS, RENDER YOU DESERVING OF THE DESERT YOUR GREATNESS DESERVES." OVER CONCEITS OF THIS SORT THE POOR GENTLEMAN LOST HIS WITS, AND USED TO LIE AWAKE STRIVING TO UNDERSTAND THEM AND WORM THE MEANING OUT OF THEM; WHAT ARISTOTLE HIMSELF COULD NOT HAVE MADE OUT OR EXTRACTED HAD HE COME TO LIFE AGAIN FOR THAT SPECIAL PURPOSE. HE WAS NOT AT ALL EASY ABOUT THE WOUNDS WHICH DON BELIANIS GAVE AND TOOK, BECAUSE IT SEEMED TO HIM THAT, GREAT AS WERE THE SURGEONS WHO HAD CURED HIM, HE MUST HAVE HAD HIS FACE AND BODY COVERED ALL OVER WITH SEAMS AND SCARS. HE COMMENDED, HOWEVER, THE AUTHOR'S WAY OF ENDING HIS BOOK WITH THE PROMISE OF THAT INTERMINABLE ADVENTURE, AND MANY A TIME WAS HE TEMPTED TO TAKE UP HIS PEN AND FINISH IT PROPERLY AS IS THERE PROPOSED, WHICH NO DOUBT HE WOULD HAVE DONE, AND MADE A SUCCESSFUL PIECE OF WORK OF IT TOO, HAD NOT GREATER AND MORE ABSORBING THOUGHTS PREVENTED HIM.
picoCTF{substitution_ciphers_are_solvable_fgnvvgndms}
人力でも解けますがquipqiup - cryptoquip and cryptogram solverなどのサイトであたりをつけてから解いたほうが速く解けます．
blaise's cipher - Points: 200
My buddy Blaise told me he learned about this cool cipher invented by a guy also named Blaise! Can you figure out what it says? Connect with nc
2018shell1.picoctf.com 18981.
アプローチ：ヴィジュネル暗号
Encrypted message:
Yse lncsz bplr-izcarpnzjo dkxnroueius zf g uzlefwpnfmeznn cousex bls ltcmaqltki my Rjzn Hfetoxea Gqmexyt axtfnj 1467 fyd axpd g rptgq nivmpr jndc zt dwoynh hjewkjy cousex fwpnfmezx. Llhjcto'x dyyypm uswy ybttimpd gqahggpty fqtkw debjcar bzrjx, lnj xhizhsey bprk nydohltki my cwttosr tnj wezypr uk ehk hzrxjdpusoitl llvmlbky tn zmp cousexypxz. Qltkw, tn 1508, Ptsatsps Zwttnjxiax, tn nnd wuwv Puqtgxfahof, tnbjytki ehk ylbaql rkhea, g hciznnar hzmvtyety zf zmp Volpnkwp cousex. Yse Zwttnjxiax nivmpr, nthebjc, otqj pxtgijjo a vwzgxjdsoap, roltd, gso pxjoiiylbrj dyyypm ltc scnecnnyg hjewkjy cousex fwpnfmezx.
Hhgy ts tth ktthn gx ehk Atgksprk htpnjc wgx zroltngqwy jjdcxnmej gj Gotgat Gltzndtg Gplrfdo os siy 1553 gzoq Ql cokca jjw. Sol. Riualn Hfetoxea Hjwlgxz. Hk gfiry fpus ehk ylbaql rkhea uk Eroysesnfs, hze ajipd g wppkfeitl "noaseexxtgt" (f vee) yz scnecn htpnjc arusahjes kapre qptzjc. Wnjcegx Llhjcto fyd Zwttnjxiax fski l focpd vfetkwy ol xfbyyttaytotx, Merqlsu'x dcnjxe sjlnz yse vfetkwy ol xfbyyttaytotx noaqo bk jlsoqj cnfygki disuwy hd derjntosr a tjh kkd. Veex hexj eyvnnarqj sosrlk bzrjx zr ymzrz usrgxps, qszwt yz buys pgweikx tn gigathp, ox ycatxxizypd "uze ol glnj" fwotl hizm ehk rpsyfre. Hjwlgxz's sjehui ehax cewztrki dtxtyg yjnuxney ltc otqj tnj vee. Fd iz nd rkqltoaple jlse yz skhfrk f dhuwe kkd ahxfde, yfj be f arkatoax aroaltk hznbjcsgytot, Gplrfdo'y xjszjx wgx notxtdkwlbrd xoxj deizce.
Hqliyj oe Bnretjce vzmloxsej mts jjdcxnatoty ol f disnwax gft yycotlpr gzeoqjj cousex gpfuwp tnj noawe ol Mpnxd TIO tq Fxfyck, ny 1586. Lgypr, os ehk 19ys ckseuxd, ehk nyvkseius zf Hjwlgxz's inahkw hay rtsgyerogftki eo Bnretjce. Jfgij Plht ny hox moup Ehk Hzdkgcegppry qlmkseej yse sndazycihzeius my yfjitl ehgy siyyzre mld "olyoxjo tnnd isuzrzfyt itytxnmuznzn gso itxeegi yasjo a xjrrkxdibj lnj jwesjytgwj cousex kzr nnx [Volpnkwp] tntfgn mp hgi yozmtnm yz du bttn ne". pohzCZK{g1gt3w3_n1pn3wd_ax3s7_maj_095glcih}
Ehk Atgksprk htpnjc ggnyej f cevzeaznzn ltc bknyg kcnevytotfwle xerusr. Nuypd gzehuw lnj rltnjxaznnigs Nhgwwey Qftcnogk Izdmxzn (Rjhiy Hlrxtwl) ifwlki ehk Atgksprk htpnjc utgcegplbrj tn nnd 1868 pojne "Zmp Arusahje Cousex" ny a imtljwpn'y rlggetnk. Ny 1917, Sinpnznqii Fxexnnat ipsiwtbki ehk Atgksprk htpnjc ay "nxpuxdihqp ol ycatxwaznzn". Zmts xjauzfeius hay szt jjdexapd. Imlrrjd Bggmamj ts qszwt yz hgap bxtvet f gaxnlnz tq tnj nivmpr gx paxqj ay 1854; mzwkapr, nj oijs'e pagwiym siy bzrq. Plsoxvi kseixjwy hwzkk yse inahkw lnj ufbrndhki ehk ypcnstqaj tn zmp 19tn hpnzzcy. Kapn hjqoxj ehox, ehuzrh, ytxe yptlrjo cxdatgsllexes itflj tncgxtotfwle gcegp ehk htpnjc it yse 16zm netyfre.
Hcyvyzgxfahoh dloip raqp uyjo ay f narhflgytot ftd hd ehk Xhiyx Lrsd mezbpet 1914 fyd 1940.
Zmp Volpnkwp cousex nd soralk jyoals tu gp a lnplj htpnjc il ne iy zdej ny cusuutheius hizm nivmpr jndky. Yse Ityfkiprgyp Szfeey tq Asjciif, qox jiasuwe, axpd g gcayx nivmpr jndk zt tmvqpmkse tnj Gimjyexj nivmpr jzcitl ehk Fxexnnat Htvoq Hax. Yse Ityfkiprghj's sjdsglps cjce lfc fxtx skhcez fyd zmp Utnzn xjrurfcle hcaippd zmpix rpsyfrey. Ysruzrhuze tnj hax, yse Ityfkiprgyp lkfoexxsiv ucisfcird cernpd auzn zmcek ppy vmcayjd, "Mgsnhkxeex Gwulk", "Nosuwezj Giiyzre" fyd, gx ehk blr ifxe zt l crtde, "Itxe Xjerogftoty".
Goqmexy Gexslm zwtej yz rkulix yse hwzkks nivmpr (iwpaznyg zmp Vkwyas–Atgksprk htpnjc it 1918), gft, tt xazypr cmlt nj oij, yse inahkw hay xeirq gursprggwe zt nreueatfwyynd. Vkwyas'x hoxp, socjgex, jgetyfarqj lki eo zmp otj-eisj aaj, f ehktceznnarqj utgcegplbrj nivmpr.
blaise's cipherはVigenere Cipherのことなので
Vigenere Solverを使います
The first well-documented description of a polyalphabetic cipher was formulated by Leon Battista Alberti around 1467 and used a metal cipher disc to switch between cipher alphabets. Alberti's system only switched alphabets after several words, and switches were indicated by writing the letter of the corresponding alphabet in the ciphertext. Later, in 1508, Johannes Trithemius, in his work Poligraphia, invented the tabula recta, a critical component of the Vigenere cipher. The Trithemius cipher, however, only provided a progressive, rigid, and predictable system for switching between cipher alphabets.
What is now known as the Vigenere cipher was originally described by Giovan Battista Bellaso in his 1553 book La cifra del. Sig. Giovan Battista Bellaso. He built upon the tabula recta of Trithemius, but added a repeating "countersign" (a key) to switch cipher alphabets every letter. Whereas Alberti and Trithemius used a fixed pattern of substitutions, Bellaso's scheme meant the pattern of substitutions could be easily changed simply by selecting a new key. Keys were typically single words or short phrases, known to both parties in advance, or transmitted "out of band" along with the message. Bellaso's method thus required strong security for only the key. As it is relatively easy to secure a short key phrase, say by a previous private conversation, Bellaso's system was considerably more secure.
Blaise de Vigenere published his description of a similar but stronger autokey cipher before the court of Henry III of France, in 1586. Later, in the 19th century, the invention of Bellaso's cipher was misattributed to Vigenere. David Kahn in his book The Codebreakers lamented the misattribution by saying that history had "ignored this important contribution and instead named a regressive and elementary cipher for him [Vigenere] though he had nothing to do with it". picoCTF{v1gn3r3_c1ph3rs_ar3n7_bad_095baccc}
The Vigenere cipher gained a reputation for being exceptionally strong. Noted author and mathematician Charles Lutwidge Dodgson (Lewis Carroll) called the Vigenere cipher unbreakable in his 1868 piece "The Alphabet Cipher" in a children's magazine. In 1917, Scientific American described the Vigenere cipher as "impossible of translation". This reputation was not deserved. Charles Babbage is known to have broken a variant of the cipher as early as 1854; however, he didn't publish his work. Kasiski entirely broke the cipher and published the technique in the 19th century. Even before this, though, some skilled cryptanalysts could occasionally break the cipher in the 16th century.
Cryptographic slide rule used as a calculation aid by the Swiss Army between 1914 and 1940.
The Vigenere cipher is simple enough to be a field cipher if it is used in conjunction with cipher disks. The Confederate States of America, for example, used a brass cipher disk to implement the Vigenere cipher during the American Civil War. The Confederacy's messages were far from secret and the Union regularly cracked their messages. Throughout the war, the Confederate leadership primarily relied upon three key phrases, "Manchester Bluff", "Complete Victory" and, as the war came to a close, "Come Retribution".
Gilbert Vernam tried to repair the broken cipher (creating the Vernam–Vigenere cipher in 1918), but, no matter what he did, the cipher was still vulnerable to cryptanalysis. Vernam's work, however, eventually led to the one-time pad, a theoretically unbreakable cipher.
サイトの詳細情報からkeyはflagということも分かります(便利)．
picoCTF{v1gn3r3_c1ph3rs_ar3n7_bad_095baccc}
hertz 2 - Points: 200
This flag has been encrypted with some kind of cipher, can you decrypt it? Connect with nc
2018shell1.picoctf.com 59771.
アプローチ：換字式暗号
Big ljayn pevht fvs djqrx voge big mwzu cvk. A ywt'b pgmagog biax ax xjyi wt gwxu revpmgq at Rayv. Ab'x wmqvxb wx af A xvmogc w revpmgq wmegwcu! Vnwu, fatg. Igeg'x big fmwk: rayvYBF{xjpxbabjbavt_yarigex_weg_bvv_gwxu_xayqabjymm}
換字式暗号っぽいのでquipqiupを使います(文量が少なく人力は難しそうなので)．
The quick bro?n fo? ?umps over the la?y dog. I can't believe this is such an easy problem in Pico. It's almost as if I solved a problem already! Okay, fine. Here's the flag: picoCTF{substitution_ciphers_are_too_easy_sicmitucll}
picoCTF{substitution_ciphers_are_too_easy_sicmitucll}
Safe RSA - Points: 250
Now that you know about RSA can you help us decrypt this ciphertext? We don't have the decryption key but something about those values looks funky..
N: 374159235470172130988938196520880526947952521620932362050308663243595788308583992120881359365258949723819911758198013202644666489247987314025169670926273213367237020188587742716017314320191350666762541039238241984934473188656610615918474673963331992408750047451253205158436452814354564283003696666945950908549197175404580533132142111356931324330631843602412540295482841975783884766801266552337129105407869020730226041538750535628619717708838029286366761470986056335230171148734027536820544543251801093230809186222940806718221638845816521738601843083746103374974120575519418797642878012234163709518203946599836959811 e: 3 ciphertext (c): 2205316413931134031046440767620541984801091216351222789180582564557328762455422721368029531360076729972211412236072921577317264715424950823091382203435489460522094689149595951010342662368347987862878338851038892082799389023900415351164773
アプローチ：Low Public Exponent Attack
eがとても小さいのでLow Public Exponent Attackが使えそうです．
Low Public Exponent Attackはeが小さいとき，nのe乗根以下の平文mについては単純に暗号文cのe乗根を取れば求めることができるというものです．
https://en.wikipedia.org/wiki/Coppersmith%27s_attack#Low_public_exponent_attack
#!/usr/bin/env python3 # -*- coding: utf-8 -*- import gmpy import codecs def root_e(c, e, n): bound = gmpy.root(n, e)[0] m = gmpy.root(c, e)[0] return m, bound if __name__ == '__main__': n = 374159235470172130988938196520880526947952521620932362050308663243595788308583992120881359365258949723819911758198013202644666489247987314025169670926273213367237020188587742716017314320191350666762541039238241984934473188656610615918474673963331992408750047451253205158436452814354564283003696666945950908549197175404580533132142111356931324330631843602412540295482841975783884766801266552337129105407869020730226041538750535628619717708838029286366761470986056335230171148734027536820544543251801093230809186222940806718221638845816521738601843083746103374974120575519418797642878012234163709518203946599836959811 e = 3 c = 2205316413931134031046440767620541984801091216351222789180582564557328762455422721368029531360076729972211412236072921577317264715424950823091382203435489460522094689149595951010342662368347987862878338851038892082799389023900415351164773 m, bound = root_e(c, e, n) print(m) print(codecs.decode(('%x'%m),'hex_codec'))
caesar cipher 2 - Points: 250
Can you help us decrypt this message? We believe it is a form of a caesar cipher. You can find the ciphertext in /problems/caesar-cipher-2_2_d9c42f8026f320079f3d4fcbaa410615 on the shell server.
PICO#4&[C!ESA2?#I0H%R3?JU34?A2%N4?S%C5R%]
アプローチ：ASCIIテーブル
messageを見るとASCIIテーブル上で32ずれてるっぽいことが分かります(PICOや[などから)
適当に変換スクリプトを書きます．
#!/usr/bin/env python3 # -*- coding: utf-8 -*- message = 'PICO#4&[C!ESA2?#I0H%R3?JU34?A2%N4?S%C5R%]' ans = [chr(ord(x) + 32) for x in message] print(''.join(ans))
picoCTF{cAesaR_CiPhErS_juST_aREnT_sEcUrE}
rsa-madlibs - Points: 250
We ran into some weird puzzles we think may mean something, can you help me solve one? Connect with nc
2018shell1.picoctf.com 40440
アプローチ：RSA関連知識
ncするとRSAに関する計算問題がでるのでそれに答えていきます．
> nc 2018shell1.picoctf.com 40440 0x7069636f4354467b64305f755f6b6e30775f7468335f7740795f325f5253405f35643338336531307dL <type 'long'> Hello, Welcome to RSA Madlibs Keeping young children entertained, since, well, nev3r Tell us how to fill in the blanks, or if it's even possible to do so Everything, input and output, is decimal, not hex #### NEW MADLIB #### q : 93187 p : 94603 ##### WE'RE GONNA NEED THE FOLLOWING #### n IS THIS POSSIBLE and FEASIBLE? (Y/N):y #### TIME TO FILL IN THE MADLIB! ### n: 8815769761 YAHHH! That one was a great madlib!!! #### NEW MADLIB #### p : 81203 n : 6315400919 ##### WE'RE GONNA NEED THE FOLLOWING #### q IS THIS POSSIBLE and FEASIBLE? (Y/N):y #### TIME TO FILL IN THE MADLIB! ### q: 77773 YAHHH! That one was a great madlib!!! #### NEW MADLIB #### e : 3 n : 12738162802910546503821920886905393316386362759567480839428456525224226445173031635306683726182522494910808518920409019414034814409330094245825749680913204566832337704700165993198897029795786969124232138869784626202501366135975223827287812326250577148625360887698930625504334325804587329905617936581116392784684334664204309771430814449606147221349888320403451637882447709796221706470239625292297988766493746209684880843111138170600039888112404411310974758532603998608057008811836384597579147244737606088756299939654265086899096359070667266167754944587948695842171915048619846282873769413489072243477764350071787327913 ##### WE'RE GONNA NEED THE FOLLOWING #### q p IS THIS POSSIBLE and FEASIBLE? (Y/N):n YAHHH! That one was a great madlib!!! #### NEW MADLIB #### q : 78203 p : 79999 ##### WE'RE GONNA NEED THE FOLLOWING #### totient(n) IS THIS POSSIBLE and FEASIBLE? (Y/N):y #### TIME TO FILL IN THE MADLIB! ### totient(n): 6256003596 YAHHH! That one was a great madlib!!! #### NEW MADLIB #### plaintext : 1815907181716474805136452061793917684000871911998851410864797078911161933431337632774829806207517001958179617856720738101327521552576351369691667910371502971480153619360010341709624631317220940851114914911751279825748 e : 3 n : 29129463609326322559521123136222078780585451208149138547799121083622333250646678767769126248182207478527881025116332742616201890576280859777513414460842754045651093593251726785499360828237897586278068419875517543013545369871704159718105354690802726645710699029936754265654381929650494383622583174075805797766685192325859982797796060391271817578087472948205626257717479858369754502615173773514087437504532994142632207906501079835037052797306690891600559321673928943158514646572885986881016569647357891598545880304236145548059520898133142087545369179876065657214225826997676844000054327141666320553082128424707948750331 ##### WE'RE GONNA NEED THE FOLLOWING #### ciphertext IS THIS POSSIBLE and FEASIBLE? (Y/N):y #### TIME TO FILL IN THE MADLIB! ### ciphertext: 26722917505435451150596710555980625220524134812001687080485341361511207096550823814926607028717403343344600191255790864873639087129323153797404989216681535785492257030896045464472300400447688001563694767148451912130180323038978568872458130612657140514751874493071944456290959151981399532582347021031424096175747508579453024891862161356081561032045394147561900547733602483979861042957169820579569242714893461713308057915755735700329990893197650028440038700231719057433874201113850357283873424698585951160069976869223244147124759020366717935504226979456299659682165757462057188430539271285705680101066120475874786208053 YAHHH! That one was a great madlib!!! #### NEW MADLIB #### ciphertext : 107524013451079348539944510756143604203925717262185033799328445011792760545528944993719783392542163428637172323512252624567111110666168664743115203791510985709942366609626436995887781674651272233566303814979677507101168587739375699009734588985482369702634499544891509228440194615376339573685285125730286623323 e : 3 n : 27566996291508213932419371385141522859343226560050921196294761870500846140132385080994630946107675330189606021165260590147068785820203600882092467797813519434652632126061353583124063944373336654246386074125394368479677295167494332556053947231141336142392086767742035970752738056297057898704112912616565299451359791548536846025854378347423520104947907334451056339439706623069503088916316369813499705073573777577169392401411708920615574908593784282546154486446779246790294398198854547069593987224578333683144886242572837465834139561122101527973799583927411936200068176539747586449939559180772690007261562703222558103359 ##### WE'RE GONNA NEED THE FOLLOWING #### plaintext IS THIS POSSIBLE and FEASIBLE? (Y/N):n YAHHH! That one was a great madlib!!! #### NEW MADLIB #### q : 92092076805892533739724722602668675840671093008520241548191914215399824020372076186460768206814914423802230398410980218741906960527104568970225804374404612617736579286959865287226538692911376507934256844456333236362669879347073756238894784951597211105734179388300051579994253565459304743059533646753003894559 p : 97846775312392801037224396977012615848433199640105786119757047098757998273009741128821931277074555731813289423891389911801250326299324018557072727051765547115514791337578758859803890173153277252326496062476389498019821358465433398338364421624871010292162533041884897182597065662521825095949253625730631876637 e : 65537 ##### WE'RE GONNA NEED THE FOLLOWING #### d IS THIS POSSIBLE and FEASIBLE? (Y/N):y #### TIME TO FILL IN THE MADLIB! ### d: 1405046269503207469140791548403639533127416416214210694972085079171787580463776820425965898174272870486015739516125786182821637006600742140682552321645503743280670839819078749092730110549881891271317396450158021688253989767145578723458252769465545504142139663476747479225923933192421405464414574786272963741656223941750084051228611576708609346787101088759062724389874160693008783334605903142528824559223515203978707969795087506678894006628296743079886244349469131831225757926844843554897638786146036869572653204735650843186722732736888918789379054050122205253165705085538743651258400390580971043144644984654914856729 YAHHH! That one was a great madlib!!! #### NEW MADLIB #### p : 153143042272527868798412612417204434156935146874282990942386694020462861918068684561281763577034706600608387699148071015194725533394126069826857182428660427818277378724977554365910231524827258160904493774748749088477328204812171935987088715261127321911849092207070653272176072509933245978935455542420691737433 ciphertext : 5315135537182226856134532843338546481354659841681272223692273789930341302489189252395544040217036010025492161730920090820789264419456405499853943420863961834511620167348215712366219204972198527365477630427263725627920265227612760416678425823843187407675643742844283110052895704455415142735463486037912801307917634230788549540802477270278755052542590491708620341889689884020271200598596327430790861785538107067664504281508756159305916221674161062222221931717498244841323828452111473034440447694160917521358885718436832783214139059379459896493819067235346238816701274408935126796953373891399167497687512301978797146598 e : 65537 n : 23952937352643527451379227516428377705004894508566304313177880191662177061878993798938496818120987817049538365206671401938265663712351239785237507341311858383628932183083145614696585411921662992078376103990806989257289472590902167457302888198293135333083734504191910953238278860923153746261500759411620299864395158783509535039259714359526738924736952759753503357614939203434092075676169179112452620687731670534906069845965633455748606649062394293289967059348143206600765820021392608270528856238306849191113241355842396325210132358046616312901337987464473799040762271876389031455051640937681745409057246190498795697239 ##### WE'RE GONNA NEED THE FOLLOWING #### plaintext IS THIS POSSIBLE and FEASIBLE? (Y/N):y #### TIME TO FILL IN THE MADLIB! ### plaintext: 240109877286251840533272915662757983981706320845661471802585807564915966910384301849411666983334013 YAHHH! That one was a great madlib!!! If you convert the last plaintext to a hex number, then ascii, you'll find what you're searching for ;)
最終問題の答えをasciiに変換するとflagになります．
picoCTF{d0_u_kn0w_th3_w@y_2_RS@_5d383e10}
計算に使用したスクリプト
#!/usr/bin/env python3 # -*- coding: utf-8 -*- import gmpy import codecs def solve1(): message = 1815907181716474805136452061793917684000871911998851410864797078911161933431337632774829806207517001958179617856720738101327521552576351369691667910371502971480153619360010341709624631317220940851114914911751279825748 e = 3 n = 29129463609326322559521123136222078780585451208149138547799121083622333250646678767769126248182207478527881025116332742616201890576280859777513414460842754045651093593251726785499360828237897586278068419875517543013545369871704159718105354690802726645710699029936754265654381929650494383622583174075805797766685192325859982797796060391271817578087472948205626257717479858369754502615173773514087437504532994142632207906501079835037052797306690891600559321673928943158514646572885986881016569647357891598545880304236145548059520898133142087545369179876065657214225826997676844000054327141666320553082128424707948750331 c = pow(message, e, n) print(c) def solve2(): q = 92092076805892533739724722602668675840671093008520241548191914215399824020372076186460768206814914423802230398410980218741906960527104568970225804374404612617736579286959865287226538692911376507934256844456333236362669879347073756238894784951597211105734179388300051579994253565459304743059533646753003894559 p = 97846775312392801037224396977012615848433199640105786119757047098757998273009741128821931277074555731813289423891389911801250326299324018557072727051765547115514791337578758859803890173153277252326496062476389498019821358465433398338364421624871010292162533041884897182597065662521825095949253625730631876637 e = 65537 l = gmpy.lcm(p-1, q-1) gcd, u, v = gmpy.gcdext(e, l) print(u) # m = pow(C, u, N) # print(m) # print(codecs.decode(('%x'%m),'hex_codec')) def solve3(): p = 153143042272527868798412612417204434156935146874282990942386694020462861918068684561281763577034706600608387699148071015194725533394126069826857182428660427818277378724977554365910231524827258160904493774748749088477328204812171935987088715261127321911849092207070653272176072509933245978935455542420691737433 ciphertext = 5315135537182226856134532843338546481354659841681272223692273789930341302489189252395544040217036010025492161730920090820789264419456405499853943420863961834511620167348215712366219204972198527365477630427263725627920265227612760416678425823843187407675643742844283110052895704455415142735463486037912801307917634230788549540802477270278755052542590491708620341889689884020271200598596327430790861785538107067664504281508756159305916221674161062222221931717498244841323828452111473034440447694160917521358885718436832783214139059379459896493819067235346238816701274408935126796953373891399167497687512301978797146598 e = 65537 n = 23952937352643527451379227516428377705004894508566304313177880191662177061878993798938496818120987817049538365206671401938265663712351239785237507341311858383628932183083145614696585411921662992078376103990806989257289472590902167457302888198293135333083734504191910953238278860923153746261500759411620299864395158783509535039259714359526738924736952759753503357614939203434092075676169179112452620687731670534906069845965633455748606649062394293289967059348143206600765820021392608270528856238306849191113241355842396325210132358046616312901337987464473799040762271876389031455051640937681745409057246190498795697239 q = n//p l = gmpy.lcm(p-1, q-1) gcd, u, v = gmpy.gcdext(e, l) while u < 0: u += l m = pow(ciphertext, u, n) print(m) print(codecs.decode(('%x'%m),'hex_codec')) if __name__ == '__main__': # solve1() # solve2() solve3()
Super Safe RSA - Points: 350
Dr. Xernon made the mistake of rolling his own crypto.. Can you find the bug and decrypt the message? Connect with nc
2018shell1.picoctf.com 1317
アプローチ：RSA is Power (SECCON BeginnersCTF 2018)
> nc 2018shell1.picoctf.com 1317 c: 1436146412347957534046107225780192646103940843567589941225217059483280549059276 n: 24116535407257621724503452906516818899123446034927680189195610304035939968688297 e: 65537
ncすると80桁(264bit)のnが降ってきます．
この程度の桁数ならラップトップでも十分素因数分解できます．
しかし，弱いアルゴリズムでは無理なのでmsieveを利用します．
> ./msieve -q -v 24116535407257621724503452906516818899123446034927680189195610304035939968688297 Msieve v. 1.53 (SVN Unversioned directory) Wed Oct 3 02:10:19 2018 random seeds: e7218537 e13b5f3e factoring 24116535407257621724503452906516818899123446034927680189195610304035939968688297 (80 digits) no P-1/P+1/ECM available, skipping commencing quadratic sieve (80-digit input) using multiplier of 1 using generic 32kb sieve core sieve interval: 12 blocks of size 32768 processing polynomials in batches of 17 using a sieve bound of 1224919 (47285 primes) using large prime bound of 122491900 (26 bits) using trial factoring cutoff of 27 bits polynomial 'A' values have 10 factors sieving in progress (press Ctrl-C to pause) 47465 relations (24001 full + 23464 combined from 261533 partial), need 47381 47465 relations (24001 full + 23464 combined from 261533 partial), need 47381 sieving complete, commencing postprocessing begin with 285534 relations reduce to 68099 relations in 2 passes attempting to read 68099 relations recovered 68099 relations recovered 57930 polynomials attempting to build 47465 cycles found 47465 cycles in 1 passes distribution of cycle lengths: length 1 : 24001 length 2 : 23464 largest cycle: 2 relations matrix is 47285 x 47465 (6.8 MB) with weight 1404341 (29.59/col) sparse part has weight 1404341 (29.59/col) filtering completed in 3 passes matrix is 33992 x 34056 (5.3 MB) with weight 1118501 (32.84/col) sparse part has weight 1118501 (32.84/col) saving the first 48 matrix rows for later matrix includes 64 packed rows matrix is 33944 x 34056 (3.4 MB) with weight 802210 (23.56/col) sparse part has weight 542953 (15.94/col) using block size 8192 and superblock size 786432 for processor cache size 8192 kB commencing Lanczos iteration memory use: 2.0 MB lanczos halted after 538 iterations (dim = 33944) recovered 17 nontrivial dependencies p39 factor: 160245102178232096945963624180811161801 p42 factor: 150497800428459168557826076453135585513697 elapsed time 00:03:51
4分弱待つと素数がふってくるので後はRSAを普通に解きます．
#!/usr/bin/env python3 # -*- coding: utf-8 -*- import gmpy import codecs if __name__ == '__main__': n = 24116535407257621724503452906516818899123446034927680189195610304035939968688297 p = 160245102178232096945963624180811161801 q = 150497800428459168557826076453135585513697 e = 65537 c = 1436146412347957534046107225780192646103940843567589941225217059483280549059276 l = gmpy.lcm(p-1, q-1) gcd, u, v = gmpy.gcdext(e, l) while u < 0: u += l m = pow(c, u, n) print(m) print(codecs.decode(('%x'%m),'hex_codec'))
> python -i solve.py
198614235373674103789367498165241205414198384663776181046663386461644141181
b'picoCTF{us3_l@rg3r_pr1m3$_0622}'
picoCTF{us3_l@rg3r_pr1m3$_0622}
ncする度に異なるnとcが降ってくるのはfactordb.com対策かな？
Super Safe RSA 2 - Points: 425
Wow, he made the exponent really large so the encryption MUST be safe, right?! Connect with nc
2018shell1.picoctf.com 47295
アプローチ：Wiener's Attack
ncすると
> nc 2018shell1.picoctf.com 47295 c: 37387925706299887988807597969592874405122472546532517291961021119819638643790973393550249580818754115056358666265075068280815261293064369821682763503666377706877846212789410720267962304506069919346315978332435305621606682564438477006652686147369852730410105272380648042992677048294641209398724334954133432228 n: 63077957037934935341227572929995254565680644759169499703819153909121991447078953877325959798681729272157579012601957115687921888781191701045447326617846201271658433913534938685175471096481583702065017512681309055288440576349117830392430063665706786284344844848310544783930682661972693701222932483974528214421 e: 52648539419443656226261340416004248287185817919210992314244038298714955737166270290730538885632379768928875742990061433773975238998122697695759864096965137020101838409616922596845976724393784055062993422652586661787336121784336273071156953454684734345903504440803713999855530184777809305216997999524795846429
eが異常に大きいですね．
なので，Wiener's Attackが使えそうです
#!/usr/bin/env python3 # -*- coding: utf-8 -*- import gmpy import codecs def continued_fraction(n, d): cf = [] while d: q = n // d cf.append(q) n, d = d, n-d*q return cf def convergents_of_contfrac(cf): n0, n1 = cf[0], cf[0]*cf[1]+1 d0, d1 = 1, cf[1] yield (n0, d0) yield (n1, d1) for i in range(2, len(cf)): n2, d2 = cf[i]*n1+n0, cf[i]*d1+d0 yield (n2, d2) n0, n1 = n1, n2 d0, d1 = d1, d2 def wieners_attack(e, n): cf = continued_fraction(e, n) convergents = convergents_of_contfrac(cf) for k, d in convergents: if k == 0: continue phi, rem = divmod(e*d-1, k) if rem != 0: continue s = n - phi + 1 # check if x^2 - s*x + n = 0 has integer roots D = s*s - 4*n if D > 0 and gmpy.is_square(D): return d if __name__ == '__main__': c = 37387925706299887988807597969592874405122472546532517291961021119819638643790973393550249580818754115056358666265075068280815261293064369821682763503666377706877846212789410720267962304506069919346315978332435305621606682564438477006652686147369852730410105272380648042992677048294641209398724334954133432228 n = 63077957037934935341227572929995254565680644759169499703819153909121991447078953877325959798681729272157579012601957115687921888781191701045447326617846201271658433913534938685175471096481583702065017512681309055288440576349117830392430063665706786284344844848310544783930682661972693701222932483974528214421 e = 52648539419443656226261340416004248287185817919210992314244038298714955737166270290730538885632379768928875742990061433773975238998122697695759864096965137020101838409616922596845976724393784055062993422652586661787336121784336273071156953454684734345903504440803713999855530184777809305216997999524795846429 d = wieners_attack(e, n) m = pow(c, d, n) print(m) print(codecs.decode(('%x'%m),'hex_codec'))
> python solve.py
264003602020102370693041857442610586342633199683725005643958437442448465210344626586049655752028764806997162365
b'picoCTF{w@tch_y0ur_Xp0n3nt$_c@r3fu11y_6498999}'
picoCTF{w@tch_y0ur_Xp0n3nt$_c@r3fu11y_6498999}
Super Safe RSA 3 - Points: 600
The more primes, the safer.. right.?.? Connect with nc
2018shell1.picoctf.com 55431.
アプローチ：Multi-Prime RSA
> nc 2018shell1.picoctf.com 55431 c: 6284728909736068686781042350032022711275028823301781180330785203125231332728727968643369066551125332455388999940520293731837668350367036978931899952068079553932753341491822687740866919455649238888041005527092011535647973767941879913564011872584207282493959651272956346317956534890056471560618411661553251 n: 26606219913940715285262138754618657144964498215833195287346927028073507527996464734239147599522486863793828606589185260368769444221246637303375795986649067159170596496643882869101122474981854051266204331512028067564886961483552840750378468416144007427323218563804469553812414257877123709505898819065167251 e: 65537
問題文的にMulti-Prime RSAかなと思ったのでmsieveなら素因数分解してくれると信じて1012bitあるnを投げました．
./msieve -q -v 26606219913940715285262138754618657144964498215833195287346927028073507527996464734239147599522486863793828606589185260368769444221246637303375795986649067159170596496643882869101122474981854051266204331512028067564886961483552840750378468416144007427323218563804469553812414257877123709505898819065167251 Msieve v. 1.53 (SVN Unversioned directory) Wed Oct 3 03:08:33 2018 random seeds: 25c78b0d 3f0ecafc factoring 26606219913940715285262138754618657144964498215833195287346927028073507527996464734239147599522486863793828606589185260368769444221246637303375795986649067159170596496643882869101122474981854051266204331512028067564886961483552840750378468416144007427323218563804469553812414257877123709505898819065167251 (305 digits) no P-1/P+1/ECM available, skipping commencing quadratic sieve (87-digit input) using multiplier of 3 using generic 32kb sieve core sieve interval: 17 blocks of size 32768 processing polynomials in batches of 12 using a sieve bound of 1467283 (56000 primes) using large prime bound of 117382640 (26 bits) using double large prime bound of 335186832815840 (41-49 bits) using trial factoring cutoff of 49 bits polynomial 'A' values have 11 factors sieving in progress (press Ctrl-C to pause) 56286 relations (16033 full + 40253 combined from 584345 partial), need 56096 56286 relations (16033 full + 40253 combined from 584345 partial), need 56096 sieving complete, commencing postprocessing begin with 600378 relations reduce to 133352 relations in 10 passes attempting to read 133352 relations recovered 133352 relations recovered 112670 polynomials attempting to build 56286 cycles found 56286 cycles in 5 passes distribution of cycle lengths: length 1 : 16033 length 2 : 11206 length 3 : 10077 length 4 : 7173 length 5 : 4954 length 6 : 3051 length 7 : 1808 length 9+: 1984 largest cycle: 19 relations matrix is 56000 x 56286 (13.8 MB) with weight 3156085 (56.07/col) sparse part has weight 3156085 (56.07/col) filtering completed in 3 passes matrix is 51220 x 51284 (12.6 MB) with weight 2903380 (56.61/col) sparse part has weight 2903380 (56.61/col) saving the first 48 matrix rows for later matrix includes 64 packed rows matrix is 51172 x 51284 (8.1 MB) with weight 2242595 (43.73/col) sparse part has weight 1623572 (31.66/col) using block size 8192 and superblock size 786432 for processor cache size 8192 kB commencing Lanczos iteration memory use: 5.0 MB lanczos halted after 811 iterations (dim = 51170) recovered 24 nontrivial dependencies p10 factor: 2219154557 p10 factor: 2387104061 p10 factor: 2405378527 p10 factor: 2544479083 p10 factor: 2613094949 p10 factor: 2799315227 p10 factor: 2816791123 p10 factor: 2834061889 p10 factor: 2844201319 p10 factor: 2928527267 p10 factor: 3003211697 p10 factor: 3016457393 p10 factor: 3028023013 p10 factor: 3053973581 p10 factor: 3117707869 p10 factor: 3118037621 p10 factor: 3420176147 p10 factor: 3447509633 p10 factor: 3449299361 p10 factor: 3505616701 p10 factor: 3638264291 p10 factor: 3671514991 p10 factor: 3822896303 p10 factor: 3828803843 p10 factor: 3886043443 p10 factor: 3890108207 p10 factor: 3923927089 p10 factor: 4018202273 p10 factor: 4120111301 p10 factor: 4201294343 p10 factor: 4233470149 p10 factor: 4254827363 elapsed time 00:10:54
11分弱待つと32個の素数を得ることができました．
あとはtotient(n)の生成を一工夫してdを計算すればflagがとれます．
#!/usr/bin/env python3 # -*- coding: utf-8 -*- import gmpy import codecs if __name__ == '__main__': c = 6284728909736068686781042350032022711275028823301781180330785203125231332728727968643369066551125332455388999940520293731837668350367036978931899952068079553932753341491822687740866919455649238888041005527092011535647973767941879913564011872584207282493959651272956346317956534890056471560618411661553251 n = 26606219913940715285262138754618657144964498215833195287346927028073507527996464734239147599522486863793828606589185260368769444221246637303375795986649067159170596496643882869101122474981854051266204331512028067564886961483552840750378468416144007427323218563804469553812414257877123709505898819065167251 e = 65537 multi_primes = [2219154557, 2387104061 ,2405378527 ,2544479083 ,2613094949 ,2799315227 ,2816791123 ,2834061889 ,2844201319 ,2928527267 ,3003211697 ,3016457393 ,3028023013 ,3053973581 ,3117707869 ,3118037621 ,3420176147 ,3447509633 ,3449299361 ,3505616701 ,3638264291 ,3671514991 ,3822896303 ,3828803843 ,3886043443 ,3890108207 ,3923927089 ,4018202273 ,4120111301 ,4201294343 ,4233470149 ,4254827363] phi = 1 for x in multi_primes: phi *= (x - 1) d = gmpy.invert(e, phi) m = pow(c, d, n) print(m) print(codecs.decode(('%x'%m),'hex_codec'))
> python solve.py
13016382529449106065908111207362094589157720258852086801305724803301206193158525
b'picoCTF{p_&_q_n0_r_$_t!!_5280799}'
picoCTF{p_&_q_n0_r_$_t!!_5280799}
まとめ
- Cryptographyは解いてて学びがありますね
- RSA関連の問題はそこそこ解けるようになったと思う
- 逆にAES関連の問題は1問も解けなかったので他の人のWrite-up読んで勉強したい
- まだ難しい問題は解けていないので暗号全般の勉強を続けていきたい
