## Welcome, To Crypto World !!!!! ⚓

I wanted to do this separate than the rest of the b0ilers 2020 bootcamp CTF writeups, since this was pretty involved/large.

Series of Mini Challenges made by @dm. There are two larger flags available if you exploit the website as well. Neither hidden challenge requires solving any of the minis. Those challenges are at the bottom of the challenge list - it is sorted by score.

http://chal.ctf.b01lers.com:1337

You will need a token to authenticate, which should have been inserted into your profile page.

This challenge contains 12*3 mini-challenges related to crypto. The
challenges are labeled by a letter A-L, indicating challenge type,
and a number 1-3, indicating difficulty.

Flag format for the mini-challenges: mini{[A-L][1-3]_[0-9,a-f]+}

The first two characters (e.g., A2) give the name of the
mini-challenge to which the flag should be submitted.

Flags in the FAKE{} format are demo flags and can not be submitted for points.

When you connect to the service, we land in an interactive story/prompt:

You can navigate via the options in the top right, which allow you to move N/E/S/W to what I’ll be calling “rooms”.

After observing all the offered rooms, I present the lay of the land:

Forgive me for any misnamed rooms/topics, I’m not a crypto guy ;P (but I’ve tried to be as accurate as possible, as learning as we go here, folks)

Solve Equations x/y Room Factor Room Bezout Room Start Room
Exp. Congruence Room   Counting Primes Room CRT Room
kth Root Modulo N Room     XOR Room
Eq. Constraint Solving Room Gandalf? Quadratic Diophantine Room Poly w/ coeff. over GF(2) Room

### Start Room ⚓

Where you land when you start the service.

• LEVEL 1: Add 1 and 1.
> ans 2
• LEVEL 2: Subtract 5 from 3.
> ans -2
• LEVEL 3: put the numbers 3, 1, 7 into increasing order.
> ans 1 3 7

COMPLETED all levels in this area.

Onwards and upwards.

#### Chinese Remainder Theorem Room ⚓

> s You went south. (Total directions from start: South)

You stop by at a small village to quench your thirst. In its pub you find a group of peasants, who are in the middle of a heated argument. As you sip your drink, you cannot help listening… is it about.. numbers?? One of them points at you and asks, “Traveler, which of us is right? Ol’ Jeff says he has a clever way to make numbers small but we think that’s just bollocks.”

Trying a problem reveals a statement that looks like needing to solve a system of congruences (“find x number that equals these numbers when modulo these numbers”), i.e Chinese Remainder Theorem.

• LEVEL 1: find a number that gives a remainder of 2 when divided by 5, a remainder of 6 when divided by 7, and a remainder of 9 when divided by 13.

So from the above code, we will stub in:

Running it, we get 412.

> ans 412

LEVEL 2: find a number that gives a remainder of 616 when divided by 1277,
a remainder of 1892 when divided by 3911, and a remainder of 3267
when divided by 6833

Alright! On to the next one; same process, just updating our numbers.

Running this gives us 6429412122.

> ans 6429412122

LEVEL 3: give the smallest positive x that satisfies x mod a_i = b_i, where

a1 = 5485948154512337139220437723513046430670172804
a2 = 2108813835706513804248871264701897235977426762
a3 = 59351473308659155928757459746804856485
a4 = 924847477382640006890848669912858050701990
a5 = 12741718618862212680555500636008445150492416265

b1 = 2661929484162718513247006741545910067104673680
b2 = 1051667267149052195100488400753935294543177150
b3 = 47216332074545827727316304129354717936
b4 = 532886655965436047074701814450039258213526
b5 = 11163090230050187304714123613300073905576382766

Again, success! This time, however, trying to run the above through the code given above results in a division/modulo by zero error. After a while, I decided to switch to using gp, which was successfull. The sequence to do so is:

Run the chinese() function against:

And then repeated call it on the remaining constraints using the resulting values:

All together in gp, it looks like:

> ans 1202114787574073135698562247558599073285047132156573830145908717087719050384755928081340071169158043961005726049447510357364537073462416777364540618918830057496883942982657669805211370184463326656

COMPLETED all levels in this area.

Woo!

#### Bezout Room ⚓

> w You went west. (Total directions from start: West)

Passing by a small town, you meet a scholar, and you two walk together for a while. He rambles about a manuscript that, he says, claims the preposterous idea that one equation could nail down two variables simultaneously. Since you show enough interest, he lets you copy a few puzzles from the book.

LEVEL 1: find integers x and y that satisfy 123x + 179y = 1

We can do this in gp again:

which gives us:

> ans -16 11

LEVEL 2: find integers x and y that satisfy 5419637592*x + 8765372543*y = 1

OK, again:

which gives us:

> ans 784426129 -485011369

LEVEL 3: give the integers x and y that satisfy a*x + b*y = c with smallest
possible |x| + |y|:

a = 172329615174258484389026493995284470243013873606078558711314460397670851456942410234121713652719725046736930219457185697597838781645377593188376635674458514137402988415274695055808334695839436438924034168872425182706138637584824074845746669005801723938330993778108851070552409088962751784310957757082836431093300116826362
b = 28356761906716612873881138710402902897347022365354411652739208693325513167251446458912103549741332079105794174802290037963900303459422464736407225394752372764336652283336292253338385760630286153548854753862316744878470244746596115894407579090226051336510357308468389580782413423780615862345700844128007232811673170490170
c = 13657769199596610482

Alright, last one, and it’s a doozy. Luckily, we still have our trusty gp ;)

which gives us the last flag for this section!

> ans -716740480992306813107503753418846234036640156759836661475354416766574545237010296962263824224509107612115141091065808866650335667339422168844609337650456083904714828583142795906730708621014510898197333708554115609551003952289103814240209709219851287729419355090392174924377596434397802758684489757519 4355772766846172289550960484253309708628309981859354451608388213582133495086922647575976048691479746491014530235602502674014803098803037825125357480987981590580196394415483266364546368978087653972266116991312510608494888084750532763692967382260459363590590286778039861513365053641201896497684198556508

COMPLETED all levels in this area.

Score!

#### Factor Room ⚓

> w You went west. (Total directions from start: West, West)

As you journey on, the weather suddenly turns and you realize that a storm is imminent. Luckily you spot a big oak tree and manage to find shelter under its canopy just in time. While the hail falls, you have time to contemplate the lectures by your old mentors. Perhaps the answers won’t elude you this time?

LEVEL 1: factor the number 48263. (E.g., for 12, you would answer 2 2 3).

OK, so looks like this room is going to be tasking our ability to factor numbers.

There’s alot of ways to factor numbers out there, and some are way faster than others, so be sure to be careful on which you choose. For this, I usually use FactorDB to check for simple values:

However, for ones that aren’t fully factored in there, we still need an alternative. Wouldn’t ya know it, we can factor in Pari/GP too! (If you haven’t caught on by now, it’s pretty awesome.)

So for our first level (which is in FactorDB, but I’ll demonstrate with gp anyways):

So:

> ans 17 17 167

LEVEL 2: factor the number 8477969543906630921459041527576694. (E.g., for 12, you would answer 2 2 3)

Which we’ll just ride the factor() train out this whole room:

so:

> ans 2 7 7 13 19 19 79 601 234490397 1655726489421517

LEVEL 3: factor the number 71142975216676910225445498956472658317166395374468624230332488059276850400024521063814543607909086075571109949

Bang! Now to really test gp:

Which ran in 5 minutes, 22 seconds on my shit ass 2014 Macbook Air laptop. Seriously guys, use Pari/gp!!!! I’m in huge debt to my teamate datajerk for introducing me to it (+1 to your beers owed counter).

So we can submit and get our last flag!:

> ans 3 11 31 29515817 1075612307646757041328543 1810939816479001125535889581 1209600061687323613153983466766686569317548327433

COMPLETED all levels in this area.

#### Counting Primes Room ⚓

> s You went south. (Total directions from start: either West, South or South, West)

As you trek through dense forest, you notice a giant snake curled up in the center of a clearing ahead. You freeze, and try to tip-toe back, but it’s too late. “Count your blessssingsss, human, for I’m not hungry… thisss time. Sssspeaking of counting… I can tell you sssecrets if you demonssstrate you are capable.

LEVEL 1: how many primes are there between 1200 and 1500?

So for this, we need to be able to count primes between two numbers. This entails actually knowing what numbers are prime and which aren’t; Knowing so is much more difficult as number value increases, especially so if you are doing a naive division check for primality.

Pari/GP offers a few prime related functions; notable for this room are isprime() and nextprime().

For the first level, we can just naively iterate over each number in the range and check if it is prime:

Which when stored in a file (count.gp) and then ran via gp count.gp, we get 43:

> ans 43

LEVEL 2: how many primes are there between 123456780 and 234567890?

Sweet! Going again with the same exact file, but changing our start and stop values, we get 5852187 (ran in about 25 seconds on my laptop!)

> ans 5852187

LEVEL 3: what is the 16th prime number after 10^400?

Awesome! Now for this last one, we can make use of the nextprime() function, which does the following:

Finds the smallest pseudoprime (see ispseudoprime) greater than or equal to x. x can be of any real type. Note that if x is a pseudoprime, this function returns x and not the smallest pseudoprime strictly larger than x. To rigorously prove that the result is prime, use isprime.

So, we can start at 10^400, and from there just continue on 15 more times (for a total of 16).

Which runs in about 2 seconds on my machine. The value it spits out for the 16th prime is:

so plugging that in, we get the last flag of this level!

> ans 10000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000018661

COMPLETED all levels in this area.

Nice!

#### XOR Room ⚓

> s You went south. (Total directions from start: South, South)

You are at a signpost, trying to figure out which path will get you through the forest. While you are contemplating, another traveller arrives. The fellow seems to know his way, so you decide to ask him. He gestures about (as if asking a question?) but you hear nothing. It is then that you realize that he cannot speak. You seem crestfallen but the traveller’s face brightens - he takes out parchment and ink from his bag and begins to write… something that looks gibberish to you. Still, you do notice some familiarity in those symbols…

LEVEL 1: the base64-encoded string below corresponds to XOR-encrypted text, with key length of 1 byte. What is the integer in the message?

PQEMSRoMChsMHUkABx0MDgwbSQAaSR0eDAcdEEQPAB8MSR0BBhwaCAcNRUkPAB8MSQEcBw0bDA1JCAcNSR0eDAUfDEc=

OK, so a basic base64 encoded string that was XOR’ed against a key that is a single byte. I’ll use xortool to solve this, specifying the key length as 1, and since we’re assumed to be working with English, I’ll guess that the most frequent char is the letter e:

OK, that sounds promising! Let’s look:

cat xortool_out/0.out
The secret integer is twenty-five thousand, five hundred and twelve.

Sweet! We got our flag:

> ans 25512

LEVEL 2: the base64-encoded string below corresponds to XOR-encrypted
text, with key length of 4 bytes. What is the integer in the
message?

BfEIGiL6CAE+900cavdJAC6zCBkvv0wLJPBdACn6CBkj60BOOPZPBj76Rxs5v0EALvZPACvrQQEk
v0kALr9MBznzQQUvv0ULJL9fBiW/SRwvv1sBav1NCT/2RAsuv0kALr9MCyfwWg8m9lILLr9KF2rr
QmrrQA8+v1wGL+YIDSvxRgE+v04BOPpbCy+/XAYvv1gPI/EIDyT7CBo48F0MJvoIGiL+XE4r7U1O
KPBdAC6/XAFq+kYdP/oTTivxTE4v7ghOHvdNTiPxXAst+lpOM/BdTj3+Rhpq9ltOe6wIGiW/XAYv
vxlfPvcIHiXoTRxk

OK, so now we get an extra fold this time: the key length is now 4 bytes instead of just 1.

For this one, I just went with the brute force (-b) option of xortool, and then inspected the 100% validity results:

Which yields:

On the other hand, we denounce with righteous indignation and dislike men who are so beguiled and demoralized by the charms of pleasure of the moment, so blinded by desire, that they cannot foresee the pain and trouble that are bound to ensue; and eq  The integer you want is 13 to the 11th power.
n t,e o0herdhan , w! de*oun'e w-th 6igh0eou7 in ign%tio* an  di7lik! me* wh+ ar! sodbeg1ile  an  de)ora(ize  bydthedcha6ms +f p(eas1re +f t,e m+men0, s+ bl-nde  byddes-re,dtha0 th!y c%nno0 fo6ese! th! pa-n a*d t6oub(e t,at %re &oun  todens1e; %nd !q  he -nte#er =ou 3antdis u3 t+ th! 110h p+werj
...
...

Which, luckily, the answer was on the first file!

“The integer you want is 13 to the 11th power.”

Send that over to get the Level 2 flag:

> ans 1792160394037

LEVEL 3: the base64-encoded file served at http://[THIS_HOST]/chal10
corresponds to XOR-encrypted text, with unknown key length.
What is the *key*, represented as a little-endian integer?

Navigating to the specified URL at /chal10, we see the following base64 text body:

Per the challenge description, the key length is unknown, and our task is finding the key that was used, and submitting it as a little-endian integer once found.

I tried various combinations of length and most expected character with xortool, but nothing seemed to yield any results. After some searching, I came across this pretty sweet tool, Ciphey. I saved the above base64 info to a file, and ran accordingly:

Sweet! So our key ended up being:

Key: 0xed98c444ea8acd9977031d048822059610297ff9e883c83d99afe04910a093

Converting that to an LE integer, we can submit accordingly:

> ans 419797111204456911416422273621730563266064217188764214578604591487313289363

COMPLETED all levels in this area.

Woo!

#### Polynomials w/ coefficient over GF(2) Room ⚓

> s You went south.

A huge basin opens up to your view, wide swathes of farmland surrounded by a ring of mountains in the distance. In the cool breeze your thoughts roam free and wild… what if those mountains are really teeth, devouring a giant wafer (the fields), and you are just an ant experiencing it all up close? You savor each possibility conjured up by your mind - one can never know when some of it comes handy.

LEVEL 1: consider polynomials in x with coefficients that are either 0 or 1. Suppose we multiply two such polynomials the usual way, except that in the result we substitute 0 for even coefficients, 1 for odd ones (this just means that coefficients live in the Galois field GF(2)). For example, (1+x)(1+x) = 1+2x+x^2 = 1+x^2. We can also map such polynomials to integers by simply taking the coefficients as a bit string. E.g., 1+x+x^4 = 1+x+0x^2+0x^3+x^4 = 11001 in binary, which is 19 in decimal. Give the integer that is the result of the multiplication 35*23 in this setup.

Doing some google searching, I found this academic page on Galois Fields in (2^m).

On that page, it mentions:

Multiplication of binary polynomials can be implemented as simple bit-shift and XOR …

As well as shows a nice example.

Doing the same with 35 and 23, we get:

100011 (35)
10111 (23)
------------
100011
1000110
10001100
000000000
1000110000
------------
1011011001

Which as a decimal, is 729.

> ans 729

LEVEL 2: consider the construction introduced in Level 1. Compute the
remainder when 250062733632176 is divided by 406399853.
I.e., convert the integers to polynomials, do the division,
and convert the result back to an integer.
(You can RESET the problem if you forgot what was in Level 1)

Nice! On that page, there’s actually even a link to a Galois Field GF(2) Calculator. We’ll use this for the second level:

Which we can convert to a decimal and then submit:

then:

> ans 90071293

LEVEL 3: consider the construction introduced in Level 1 that mapped
polynomials to integers. Find the solution to the equation
a*y^2 + b*y + c = 0 in that setup, where

a = 62988136202118127274037485756847228824659813916854388288704528975265641038375
b = 61970982425686765788241036465223359125124685363948286523458864616239704859380
c = 16032512672834824306563461964216557396271213056568232093692714812022221106419800157218922185040829131491280726002257183375575408421728567246659014589764356633340492085105583082470307172750166547566757359700457224812429817166783751

Damn! That’s a big number. I didn’t have time to look back it this one, so no solve :\

> w You went west. (Total directions from start: South, South, South, West)

You make camp by a delapidated building that must have been a shrine in its better days. As the rays of the setting sun illuminate the walls, you notice a crevice with a piece of parchment tucked inside… a treasure map! Though you cannot quite make out which direction is east or west, and north or south, on the map, this could be payday - provided you figure out the right number of steps to take.

LEVEL 1: find positive integers x, y that solve x^2 + 22*y^2 = 8383

Solving an equation for X and Y given constraints, enter, Z3 theorem solver!

Seriously. Using Z3 for this Room made the entire thing trivial. Just define our two X and Y variables, and then stub in the value for each level and we get all three flags for free:

Submitting:

> ans 21 19

LEVEL 2: find positive integers x, y that solve x^2 + 608268054*y^2 = 288964812689493391976023993

Now back to Z3:

Submitting:

> ans 729485423 689247146

LEVEL 3: find positive integers x, y that solve x^2 + a*y^2 = b, where

a = 809575361919189873249985593557526797315607233589
b = 453911665595804740746927043910783828583622477123414312540919542168796850447209357992143785144169862380534061054229556425568794584043785497763918

One last time with Z3:

And submitting:

> ans 822249775978922834074863312050877571308123090437 748784818951812933713395251176142145550673582079

COMPLETED all levels in this area.

Z3 FTW.

#### Gandalf? ⚓

> w You went east.

To the north is a narrow bridge that leads to the tower of the Greatest Crypto
Wizard of the land. Or, what remained of the bridge… Crossing the chasm
below is surely impossible. A sign by the bridge says “You shall not pass.”

Trying to move “north” isn’t allowed. Not sure what this room was about, didn’t have time to explore it more, if it was actually something.

#### Equation Constraint Solving Room ⚓

> w You went west.

You see an inn and decide that you deserve to splurge some on a good meal and
a comfy bed. The room is tidy and clean but you do notice certain little
visitors… mice. Fear not, the innkeeper’s cat comes eagerly to your rescue.
But whenever it tries to catch one, the mouse quickly disappears in one of
many mouseholes in the room. With this game going on and on for minutes, you
swear those mice must be playing with the cat. Interesting, you think, there
must be a smarter way to capture small creatures…

LEVEL 1: find small nonzero integers x, y, z that satisfy 299x + 355y + 251z = 0
(e.g., x = 355
251, y = 299251, z = -2299*355 does not count)

Enter: Z3, again! We can plug these values into a Z3 solver with our contraints:

• Must be non-zero
• “small” (NGL – This was kind of a dick move, could have just specified with more precision this constraint, and not just “small”)

With some guessing on how small the values had to be, we get the following Z3 goodness:

Which when ran, gives us:

python solver.py
sat
[z = -7, y = -6, x = 13]

After submitting:

> ans 13 -6 -7
LEVEL 2: find small nonzero integers x, y, z that satisfy a*x + b*y + c*z = 0,
where a=69925405969, b=48507179354, c=32417688895

OK. After editing our Z3 code from above with the new a, b, and c values, and no size constraint, we get:

python solver.py
sat
[z = -69925405969, y = -69925405969, x = 80924868249]

Unfortunately, that’s likely not “small”, so we need to go back and now try to restrict our x/y/z size until we find something that the problem likes.

I tried first constraining x/y/z to be all less than 1000, but after running for about 70 minutes, Z3 came back with unsat (i.e not possible).

So, I then bumped the constraints up to be 1000000, and Z3 came back with an answer in a few seconds:

Which submitting, works:

> ans 672945 -951115 -28381

LEVEL 3: find nonzero integers v, w, x, y, z with a minimal sum of squares
that satisfy a*v + b*w + c*x + d*y + e*z = 0, where

a= 13224482656452729965010130774472519546513322282685222044383028560173414320699907502364037066998078684364749338920872578811245752029508639952579415409556998
b= 11883954373554361547375474750630839024678353968736077156027924497730635501467831406890604708209797932039373450099216323200104673509462816247739552390501700
c= 12033890847356726156410304461564041151269011907532227202193795241332802954932830212451456439198182308280974025227196605722871001660179705508977260220793964
d= 2844873315637923430702813720068362602065731767047450571384220379074997608589211929239202046737041926913187483721774104817975966051912270671035046621837635
e= 2606527713655043968153387630347865477764170887107821220448557599575906298221841101758877277715742039004267346644911989983884822836245158485633146455362314

OK - last level, same concept, except now more constraints, and much larger values. I was not able to solve this one in time, was working on other rooms.

#### kth Root Modulo N Room ⚓

> n You went north. (Total directions from start: South, South, South, West, West, West, North)

Higher up on the hillside you come across a small house with a tidy garden. An elderly rabbit lady in a rocking chair is observing you, while she nibbles on some sort of brown root (carrot maybe?). “Have some, my dear” she says, “great for vision.” You oblige, and indeed, as if finer distinctions started to materialize in things. “Now we just need to calibrate the dose,” says the rabbit and gives you something colorful to peer into.

LEVEL 1: find an integer that satisfies x^2 mod 97 = 88

OK, so we need to find the square root over modulo 97 that equals to 88.

Which we can use like so:

Which gives us 66.

> ans 66

LEVEL 2: find an integer that satisfies x^2 mod 1359203501 = 95422207

OK, repeating the above but with our new numbers gives us 810550192.

> ans 810550192

LEVEL 3: give the smallest positive x for which x^12 mod p = a, where

a = 1817525449797280602402956873386237720889680621662448878394577537780771524786955876245638699592180826704996032326091618875207339103593277472500067216389870
p = 12779849905941677959186610420316494198424452561778642658582451521063175469853171114961122342052464710078864014592127176275630898014968982060325361045608439

Damn, no more square root. Now we have to work with the 12th root (x^12). So our python code from above won’t work.

#### Exponential Congruence Room ⚓

> n You went north.

As dusk falls you make camp at a logging area. There are tree stumps everywhere, some truly gigantic ones too. You are just about to fall asleep when you hear footsteps - one of the fellers came back for his axe. He moves sluggishly as if his limbs were made of lead, totally obliviously to your presence. As he leaves you catch him grumbling about how hard this line of work is. Your eyes close and you dream, of something quite peculiar…

LEVEL 1: find an integer that satisfies 11^x mod 101 = 27 (here ^ means exponentiation, e.g., 2^7 mod 5 = 3)

Simple brute force will work for the first one:

> ans 39

And I ran out of time to come back to the second one.

#### Solve Equations x/y Room ⚓

> w You went west.

The road curves and gives way to marshland. You tread by one careful
step after another, focused so much on your footings that you only notice the
lizardman when he starts talking to you. “Hello, I am in the Enformation
Commerce. We two must have things to trade.” He needs help with math to break
some encrypted messages.

LEVEL 1: solve the equations below for x and y

(76*x + 221*y) mod 281 = 85
(171*x + 190*y) mod 281 = 138

I did not have any time at all to look at this room, but it looks like it’s solving a system of congruences, but with a fold where the value is now consistent of x and y that need to be solved for, in combination with the congruences.