Prime
9 minutes to read
We are given the source code of the server in SageMath:
import gmpy2
import random
from secret import FLAG
def main():
n = int(input("prime: "))
if n <= 0:
print("No mystiz trick")
elif n.bit_length() < 256 or n.bit_length() > 512:
print("Not in range")
elif not is_prime(n):
print("Not prime")
else:
x = int(input("factor: "))
if x > 1 and x < n and n % x == 0:
print("You got me")
print(FLAG)
else:
print("gg")
def is_prime(n):
# check if n = a^b for some a, b > 1
for i in range(2, n.bit_length()):
root, is_exact = gmpy2.iroot(n, i)
if is_exact:
return False
rs = [2, 3, 5, 7, 11, 13, 17, 19, 23, 29, 31, 37, 41, 43, 47, 53, 59, 61, 67, 71, 73, 79, 83, 89, 97]
return all(test(n, r) for r in rs)
def test(n, r):
"""
check whether `(x + a) ^ n = x ^ n + a (mod x ^ r - 1)` in Z/nZ for some `a`.
"""
R.<x> = Zmod(n)[]
S = R.quotient_ring(x ^ r - 1)
a = 1 + random.getrandbits(8)
if S(x + a) ^ n != S(x ^ (n % r)) + a:
return False
return True
if __name__ == "__main__":
main()
Source code analysis
The script implements the AKS primality test, and asks for a prime number that has a factor different than
def main():
n = int(input("prime: "))
if n <= 0:
print("No mystiz trick")
elif n.bit_length() < 256 or n.bit_length() > 512:
print("Not in range")
elif not is_prime(n):
print("Not prime")
else:
x = int(input("factor: "))
if x > 1 and x < n and n % x == 0:
print("You got me")
print(FLAG)
else:
print("gg")
def is_prime(n):
# check if n = a^b for some a, b > 1
for i in range(2, n.bit_length()):
root, is_exact = gmpy2.iroot(n, i)
if is_exact:
return False
If so happens, the server will show the flag. But this is a contradiction, since a prime number is only divisible by
AKS primality test
First of all, we need to do a bit of research on the AKS primality test. I found good information on these resources:
Basically, the test is built from Fermat’s Little Theorem, where
Because
The AKS test uses also an irreducible polynomial to make computation more efficient, that is:
Applying modulo
According to PRIMES is in P, these are the steps of the AKS algorithm:
Input: integer
.
- If
for and , output COMPOSITE. - Find the smallest
such that . - If
for some , output COMPOSITE. - If
, output PRIME. - For
to do if , output COMPOSITE; - Output PRIME.
The implementation mistake
We have seen that AKS test is deterministic, so how are we going to break it? Well, this is just a vulnerable implementation:
def is_prime(n):
# check if n = a^b for some a, b > 1
for i in range(2, n.bit_length()):
root, is_exact = gmpy2.iroot(n, i)
if is_exact:
return False
rs = [2, 3, 5, 7, 11, 13, 17, 19, 23, 29, 31, 37, 41, 43, 47, 53, 59, 61, 67, 71, 73, 79, 83, 89, 97]
return all(test(n, r) for r in rs)
def test(n, r):
"""
check whether `(x + a) ^ n = x ^ n + a (mod x ^ r - 1)` in Z/nZ for some `a`.
"""
R.<x> = Zmod(n)[]
S = R.quotient_ring(x ^ r - 1)
a = 1 + random.getrandbits(8)
if S(x + a) ^ n != S(x ^ (n % r)) + a:
return False
return True
There are two things in this implementation that differ from the algorithm:
- The SageMath script tests several
values (all prime numbers lower than ), whereas the AKS algorithm suggests looking for a specific value of (step 2) - The SageMath script takes a random
for the test, whereas the AKS algorithm iterates from to (step 5)
Breaking the AKS implementation
It is not clear what can happen if
After researching on how to break primality tests, we can find Carmichael numbers. These are composite numbers that satisfy Fermat’s Little Theorem. In other words,
Let’s try it:
$ sage -q
sage: import gmpy2
....: import random
sage:
sage: def test(n, r):
....: """
....: check whether `(x + a) ^ n = x ^ n + a (mod x ^ r - 1)` in Z/nZ for some `a`.
....: """
....: R.<x> = Zmod(n)[]
....: S = R.quotient_ring(x ^ r - 1)
....:
....: a = 1 + random.getrandbits(8)
....: if S(x + a) ^ n != S(x ^ (n % r)) + a:
....: return False
....: return True
....:
sage: test(561, 2)
True
sage: test(561, 3)
False
sage: test(561, 4)
False
sage: test(561, 5)
False
sage: test(1105, 2)
True
sage: test(1105, 3)
False
sage: test(1729, 2)
True
sage: test(1729, 3)
True
sage: test(1729, 5)
False
Finding Carmichael numbers
Some Carmichael numbers output True
, we might be on the right track. There is a way to generate some Carmichael numbers: If
$ python3 -q
>>> from Crypto.Util.number import isPrime
>>>
>>> for k in range(1000):
... if isPrime(6 * k + 1) and isPrime(12 * k + 1) and isPrime(18 * k + 1):
... print(k, (6 * k + 1) * (12 * k + 1) * (18 * k + 1))
...
1 1729
6 294409
35 56052361
45 118901521
51 172947529
55 216821881
56 228842209
100 1299963601
121 2301745249
195 9624742921
206 11346205609
216 13079177569
255 21515221081
276 27278026129
370 65700513721
380 71171308081
426 100264053529
506 168003672409
510 172018713961
511 173032371289
710 464052305161
741 527519713969
800 663805468801
825 727993807201
871 856666552249
930 1042789205881
975 1201586232601
Let’s try the last one with all
sage: rs = [2, 3, 5, 7, 11, 13, 17, 19, 23, 29, 31, 37, 41, 43, 47, 53, 59, 61, 67, 71, 73, 79, 83, 89, 97]
sage: [(r, test(1201586232601, r)) for r in rs]
[(2, True),
(3, True),
(5, True),
(7, False),
(11, False),
(13, True),
(17, False),
(19, False),
(23, False),
(29, False),
(31, False),
(37, False),
(41, False),
(43, False),
(47, False),
(53, False),
(59, False),
(61, False),
(67, False),
(71, False),
(73, False),
(79, False),
(83, False),
(89, False),
(97, False)]
As can be seen, for
After a lot of tests with bigger Carmichael numbers, I found out that the test fails when
In the previous example,
Solution
So, we need a number
>>> from math import prod
>>>
>>> rs = [2, 3, 5, 7, 11, 13, 17, 19, 23, 29, 31, 37, 41, 43, 47, 53, 59, 61, 67, 71, 73, 79, 83, 89, 97]
>>> k_0 = prod(rs[2:])
>>> k_0
384261327324253070792183691221959345
>>>
>>> m = 1
>>> while True:
... k = m * k_0
... m += 1
... if isPrime(6 * k + 1) and isPrime(12 * k + 1) and isPrime(18 * k + 1):
... print(k, (6 * k + 1) * (12 * k + 1) * (18 * k + 1))
... break
...
141792429782649383122315782060902998305 3694572010169851255631956434046586025725603891058582291439147359413655694039141973775417050450842378469305302694178881
There we have one candidate, and it breaks the test:
sage: [(r, test(3694572010169851255631956434046586025725603891058582291439147359413655694039141973775417050450842378469305302694178881, r)) for r in rs]
[(2, True),
(3, True),
(5, True),
(7, True),
(11, True),
(13, True),
(17, True),
(19, True),
(23, True),
(29, True),
(31, True),
(37, True),
(41, True),
(43, True),
(47, True),
(53, True),
(59, True),
(61, True),
(67, True),
(71, True),
(73, True),
(79, True),
(83, True),
(89, True),
(97, True)]
Flag
Now that we have a Carmichael number that breaks the test and the corresponding
$ nc prime.balsnctf.com 10003
prime: 3694572010169851255631956434046586025725603891058582291439147359413655694039141973775417050450842378469305302694178881
factor: 850754578695896298733894692365417989831
You got me
BALSN{th3_imp1_15_bR0k3n_4nd_mUch_sL0W3r_tH4n_pycrypto_is_prime_qwq}