MODULAR ARITHMETIC
shenghuo2A fun, free platform for learning modern cryptography
MODULAR ARITHMETIC
Greatest Common Divisor
The Greatest Common Divisor (GCD), sometimes known as the highest common factor, is the largest number which divides two positive integers (a,b).
For $a = 12, b = 8$ we can calculate the divisors of a: ${1,2,3,4,6,12}$ and the divisors of b: ${1,2,4,8}$. Comparing these two, we see that $gcd(a,b) = 4$.
Now imagine we take $a = 11, b = 17$. Both $a$ and $b$ are prime numbers. As a prime number has only itself and $1$ as divisors, $gcd(a,b) = 1$.
We say that for any two integers $a,b$, if $gcd(a,b) = 1$ then $a$ and $b$ are coprime integers.
If $a$ and $b$ are prime, they are also coprime. If $a$ is prime and $b < a$ then $a$ and $b$ are coprime.
Think about the case for $a$ prime and $b > a$, why are these not necessarily coprime?
There are many tools to calculate the GCD of two integers, but for this task we recommend looking up Euclid’s Algorithm.
Try coding it up; it’s only a couple of lines. Use $a = 12, b = 8$ to test it.
Now calculate $gcd(a,b)$ for $a = 66528, b = 52920$ and enter it below.
|
|
|
|
Extended GCD
Let $a$ and $b$ be positive integers.
The extended Euclidean algorithm is an efficient way to find integers $u,v$ such that
1a * u + b * v = gcd(a,b)Later, when we learn to decrypt RSA, we will need this algorithm to calculate the modular inverse of the public exponent.
Using the two primes $p = 26513, q = 32321$, find the integers $u,v$ such that
1p * u + q * v = gcd(p,q)Enter whichever of $u$ and $v$ is the lower number as the flag.
Knowing that $p,q$ are prime, what would you expect $gcd(p,q)$ to be? For more details on the extended Euclidean algorithm, check out this page.
|
|
|
|
Modular Arithmetic 1
Imagine you lean over and look at a cryptographer’s notebook. You see some notes in the margin:
4 + 9 = 1 5 - 7 = 10 2 + 3 = 5
At first you might think they’ve gone mad. Maybe this is why there are so many data leaks nowadays you’d think, but this is nothing more than modular arithmetic modulo 12 (albeit with some sloppy notation).
You may not have been calling it modular arithmetic, but you’ve been doing these kinds of calculations since you learnt to tell the time (look again at those equations and think about adding hours).
Formally, “calculating time” is described by the theory of congruences. We say that two integers are congruent modulo m if $a ≡ b mod m$.
Another way of saying this, is that when we divide the integer $a$ by $m$, the remainder is $b$. This tells you that if m divides a (this can be written as $m | a$) then $a ≡ 0 mod m$.
Calculate the following integers:
11 ≡ x mod 6 8146798528947 ≡ y mod 17
The solution is the smaller of the two integers.
|
|
|
|
Modular Arithmetic 2
We’ll pick up from the last challenge and imagine we’ve picked a modulus $p$, and we will restrict ourselves to the case when $p$ is prime.
The integers modulo $p$ define a field, denoted $F_p$.
If the modulus is not prime, the set of integers modulo $n$ define a ring.
A finite field $F_p$ is the set of integers ${0,1,…,p-1}$, and under both addition and multiplication there is an inverse element $b$ for every element $a$ in the set, such that $a + b = 0$ and $a * b = 1$.
Note that the identity element for addition and multiplication is different! This is because the identity when acted with the operator should do nothing: $a + 0 = a$ and $a * 1 = a$.
Lets say we pick $p = 17$. Calculate $3^{17} mod 17$. Now do the same but with $5^{17} mod 17$.
What would you expect to get for $7^{16} mod 17$? Try calculating that.
This interesting fact is known as Fermat’s little theorem. We’ll be needing this (and its generalisations) when we look at RSA cryptography.
Now take the prime $p = 65537$. Calculate $273246787654^{65536} mod 65537$.
Did you need a calculator?
|
|
Modular Inverting
As we’ve seen, we can work within a finite field $F_p$, adding and multiplying elements, and always obtain another element of the field.
For all elements $g$ in the field, there exists a unique integer $d$ such that $g * d ≡ 1 mod p$.
This is the multiplicative inverse of $g$.
Example: $7 * 8 = 56 ≡ 1 mod 11$
What is the inverse element: $3 * d ≡ 1 mod 13$?
|
|
Quadratic Residues
We’ve looked at multiplication and division in modular arithmetic, but what does it mean to take the square root modulo an integer?
For the following discussion, let’s work modulo $p = 29$. We can take the integer $a = 11$ and calculate $a^2 = 5 mod 29$.
As $a = 11, a^2 = 5$, we say the square root of $5$ is $11$.
This feels good, but now let’s think about the square root of $18$. From the above, we know we need to find some integer $a$ such that $a^2 = 18$
Your first idea might be to start with $a = 1$ and loop to $a = p-1$. In this discussion $p$ isn’t too large and we can quickly look.
Have a go, try coding this and see what you find. If you’ve coded it right, you’ll find that for all $a ∈ F_p^*$ you never find an $a$ such that $a^2 = 18$.
What we are seeing, is that for the elements of $F^_p$, not every element has a square root. In fact, what we find is that for roughly one half of the elements of $F_p^$, there is no square root.
We say that an integer $x$ is a Quadratic Residue if there exists an $a$ such that $a2 = x mod p$. If there is no such solution, then the integer is a Quadratic Non-Residue.
In other words, $x$ is a quadratic residue when it is possible to take the square root of $x$ modulo an integer $p$.
In the below list there are two non-quadratic residues and one quadratic residue.
Find the quadratic residue and then calculate its square root. Of the two possible roots, submit the smaller one as the flag.
If $a^2 = x$ then $(-a)^2 = x$. So if $x$ is a quadratic residue in some finite field, then there are always two solutions for $a$.
1 2p = 29 ints = [14, 6, 11]
|
|
|
|
Legendre Symbol
In Quadratic Residues we learnt what it means to take the square root modulo an integer. We also saw that taking a root isn’t always possible.
In the previous case when $p = 29$, even the simplest method of calculating the square root was fast enough, but as $p$ gets larger, this method becomes wildly unreasonable.
Lucky for us, we have a way to check whether an integer is a quadratic residue with a single calculation thanks to Legendre. In the following, we will assume we are working modulo a prime $p$.
Before looking at Legendre’s symbol, let’s take a brief detour to see an interesting property of quadratic (non-)residues.
Quadratic Residue * Quadratic Residue = Quadratic Residue Quadratic Residue * Quadratic Non-residue = Quadratic Non-residue Quadratic Non-residue * Quadratic Non-residue = Quadratic Residue
Want an easy way to remember this? Replace “Quadratic Residue” with $+1$ and “Quadratic Non-residue” with $-1$, all three results are the same!
So what’s the trick? The Legendre Symbol gives an efficient way to determine whether an integer is a quadratic residue modulo an odd prime $p$.
Legendre’s Symbol: $(a / p) ≡ a^{(p-1)/2} mod p$ obeys:
(a / p) = 1 if a is a quadratic residue and a ≢ 0 mod p (a / p) = -1 if a is a quadratic non-residue mod p (a / p) = 0 if a ≡ 0 mod p
Which means given any integer $a$, calculating $pow(a,(p-1)//2,p)$ is enough to determine if $a$ is a quadratic residue.
Now for the flag. Given the following 1024 bit prime and 10 integers, find the quadratic residue and then calculate its square root; the square root is your flag. Of the two possible roots, submit the larger one as your answer.
So Legendre’s symbol tells us which integer is a quadratic residue, but how do we find the square root?! The prime supplied obeys $p = 3 mod 4$, which allows us easily compute the square root. The answer is online, but you can figure it out yourself if you think about Fermat’s little theorem.
|
|
|
|
Modular Square Root
In Legendre Symbol we introduced a fast way to determine whether a number is a square root modulo a prime. We can go further: there are algorithms for efficiently calculating such roots. The best one in practice is called Tonelli-Shanks, which gets its funny name from the fact that it was first described by an Italian in the 19th century and rediscovered independently by Daniel Shanks in the 1970s.
All primes that aren’t 2 are of the form $p ≡ 1 mod 4$ or $p ≡ 3 mod 4$, since all odd numbers obey these congruences. As the previous challenge hinted, in the $p ≡ 3 mod 4$ case, a really simple formula for computing square roots can be derived directly from Fermat’s little theorem. That leaves us still with the $p ≡ 1 mod 4$ case, so a more general algorithm is required.
In a congruence of the form $r2 ≡ a mod p$, Tonelli-Shanks calculates $r$.
Tonelli-Shanks doesn’t work for composite (non-prime) moduli. Finding square roots modulo composites is computationally equivalent to integer factorization - that is, it’s a hard problem.
The main use-case for this algorithm is finding elliptic curve co-ordinates. Its operation is somewhat complex so we’re not going to discuss the details, however, implementations are easy to find and Sage has one built-in.
Find the square root of $a$ modulo the 2048-bit prime $p$. Give the smaller of the two roots as your answer.
|
|
|
|
Chinese Remainder Theorem
The Chinese Remainder Theorem gives a unique solution to a set of linear congruences if their moduli are coprime.
This means, that given a set of arbitrary integers $a_i$, and pairwise coprime integers $ni$, such that the following linear congruences hold:
Note “pairwise coprime integers” means that if we have a set of integers ${n_1, n_2, …, n_i}$, all pairs of integers selected from the set are coprime: $gcd(ni, nj) = 1$.
x ≡ a1 mod N1 x ≡ a2 mod N2 … x ≡ an mod Nn
There is a unique solution $x ≡ a mod N$ where $N = n_1 * n_2 * … * n_n$.
In cryptography, we commonly use the Chinese Remainder Theorem to help us reduce a problem of very large integers into a set of several, easier problems.
Given the following set of linear congruences:
x ≡ 2 mod 5 x ≡ 3 mod 11 x ≡ 5 mod 17
Find the integer $a$ such that $x ≡ a mod 935$
Starting with the congruence with the largest modulus, use that for $x ≡ a mod p$ we can write $x = a + k*p$ for arbitrary integer $k$.
|
|
|
|
Adrien’s Signs
Adrien’s been looking at ways to encrypt his messages with the help of symbols and minus signs. Can you find a way to recover the flag?
1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 16 17 18 19 20 21 22 23from random import randint a = 288260533169915 p = 1007621497415251 FLAG = b'crypto{????????????????????}' def encrypt_flag(flag): ciphertext = [] plaintext = ''.join([bin(i)[2:].zfill(8) for i in flag]) for b in plaintext: e = randint(1, p) n = pow(a, e, p) if b == '1': ciphertext.append(n) else: n = -n % p ciphertext.append(n) return ciphertext print(encrypt_flag(FLAG))
1[67594220461269, 501237540280788, 718316769824518, 296304224247167, 48290626940198, 30829701196032, 521453693392074, 840985324383794, 770420008897119, 745131486581197, 729163531979577, 334563813238599, 289746215495432, 538664937794468, 894085795317163, 983410189487558, 863330928724430, 996272871140947, 352175210511707, 306237700811584, 631393408838583, 589243747914057, 538776819034934, 365364592128161, 454970171810424, 986711310037393, 657756453404881, 388329936724352, 90991447679370, 714742162831112, 62293519842555, 653941126489711, 448552658212336, 970169071154259, 339472870407614, 406225588145372, 205721593331090, 926225022409823, 904451547059845, 789074084078342, 886420071481685, 796827329208633, 433047156347276, 21271315846750, 719248860593631, 534059295222748, 879864647580512, 918055794962142, 635545050939893, 319549343320339, 93008646178282, 926080110625306, 385476640825005, 483740420173050, 866208659796189, 883359067574584, 913405110264883, 898864873510337, 208598541987988, 23412800024088, 911541450703474, 57446699305445, 513296484586451, 180356843554043, 756391301483653, 823695939808936, 452898981558365, 383286682802447, 381394258915860, 385482809649632, 357950424436020, 212891024562585, 906036654538589, 706766032862393, 500658491083279, 134746243085697, 240386541491998, 850341345692155, 826490944132718, 329513332018620, 41046816597282, 396581286424992, 488863267297267, 92023040998362, 529684488438507, 925328511390026, 524897846090435, 413156582909097, 840524616502482, 325719016994120, 402494835113608, 145033960690364, 43932113323388, 683561775499473, 434510534220939, 92584300328516, 763767269974656, 289837041593468, 11468527450938, 628247946152943, 8844724571683, 813851806959975, 72001988637120, 875394575395153, 70667866716476, 75304931994100, 226809172374264, 767059176444181, 45462007920789, 472607315695803, 325973946551448, 64200767729194, 534886246409921, 950408390792175, 492288777130394, 226746605380806, 944479111810431, 776057001143579, 658971626589122, 231918349590349, 699710172246548, 122457405264610, 643115611310737, 999072890586878, 203230862786955, 348112034218733, 240143417330886, 927148962961842, 661569511006072, 190334725550806, 763365444730995, 516228913786395, 846501182194443, 741210200995504, 511935604454925, 687689993302203, 631038090127480, 961606522916414, 138550017953034, 932105540686829, 215285284639233, 772628158955819, 496858298527292, 730971468815108, 896733219370353, 967083685727881, 607660822695530, 650953466617730, 133773994258132, 623283311953090, 436380836970128, 237114930094468, 115451711811481, 674593269112948, 140400921371770, 659335660634071, 536749311958781, 854645598266824, 303305169095255, 91430489108219, 573739385205188, 400604977158702, 728593782212529, 807432219147040, 893541884126828, 183964371201281, 422680633277230, 218817645778789, 313025293025224, 657253930848472, 747562211812373, 83456701182914, 470417289614736, 641146659305859, 468130225316006, 46960547227850, 875638267674897, 662661765336441, 186533085001285, 743250648436106, 451414956181714, 527954145201673, 922589993405001, 242119479617901, 865476357142231, 988987578447349, 430198555146088, 477890180119931, 844464003254807, 503374203275928, 775374254241792, 346653210679737, 789242808338116, 48503976498612, 604300186163323, 475930096252359, 860836853339514, 994513691290102, 591343659366796, 944852018048514, 82396968629164, 152776642436549, 916070996204621, 305574094667054, 981194179562189, 126174175810273, 55636640522694, 44670495393401, 74724541586529, 988608465654705, 870533906709633, 374564052429787, 486493568142979, 469485372072295, 221153171135022, 289713227465073, 952450431038075, 107298466441025, 938262809228861, 253919870663003, 835790485199226, 655456538877798, 595464842927075, 191621819564547]
|
|
Modular Binomials
Rearrange the following equations to get the primes
p,q$N = pq$ $c_1 = (2p + 3q)^{e_1} mod N$ $c_2 = (5p + 7q)^{e_2} mod N$
$N = p*q$
$c1 = (2p+3q)^{e1} mod N$
$c_2 = (5p + 7q)^{e_2} mod N$
$\Downarrow$
$c_1^{e_2} = (2p + 3q)^{(e_1e_2)}\ mod\ N$
$c_2^{e_1} = (5p + 7q)^{(e_1e_2)}\ mod\ N$
$\Downarrow$
$f_1 = 5^{e_1e_2} * c_1^{e_2} = (10p + 15q)^{(e_1e_2)}\ mod \ N$
$f_2 = 2^{e_1e_2} * c_2^{e_1} = (10p + 14q)^ {(e_1e_2)}\ mod \ N$
$\Downarrow$
$f_1-f_2=q^{(e_1*e_2)}\ mod\ N$
$q = gcd((f_1-f_2),N)$
|
|
|
|