Challenge
Copy def f(s, p):
u = 0
for i in range(p):
u += p - i
u *= s
u %= p
return u
p = getPrime(1024)
s = random.randint(1, p - 1)
A = f(s, p)
Given the value of p and A, we have to find the value of s, which is used in encrypting the flag
f(s,p) generates a polynomial of the form
f ( s , p ) = ( ∑ i = 0 p − 1 ( p − i ) ⋅ s i ) m o d     p f(s, p) = \left( \sum_{i=0}^{p-1} (p - i) \cdot s^{i} \right) \mod p f ( s , p ) = ( i = 0 ∑ p − 1 ​ ( p − i ) ⋅ s i ) mod p Since it is under modulo p, therefore we can write the polynomial as
f ( s , p ) = ( ∑ i = 0 p − 1 ( − i ) ⋅ s i ) m o d     p f(s, p) = \left( \sum_{i=0}^{p-1} (- i) \cdot s^{i} \right) \mod p f ( s , p ) = ( i = 0 ∑ p − 1 ​ ( − i ) ⋅ s i ) mod p On expanding, we get
f ( s , p ) = − ( 1 ⋅ s 1 + 2 ⋅ s 2 + 3 ⋅ s 3 + . . . + ( p − 1 ) ⋅ s p − 1 ) m o d     p \quad f(s, p) = - \left( 1 \cdot s^{1} + 2 \cdot s^{2} + 3 \cdot s^{3} + ... + (p-1) \cdot s^{p-1} \right) \mod p f ( s , p ) = − ( 1 ⋅ s 1 + 2 ⋅ s 2 + 3 ⋅ s 3 + ... + ( p − 1 ) ⋅ s p − 1 ) mod p This form of series is known as an AGP series or arithmetico-geometric progression. While there is a direct formula to calculate the sum of the series, in this case, it is easier to use the method which is used to derive the formula to solve rather then substituting into the formula itself.
L e t 2 f ( s , p ) = − ( 1 ⋅ s 1 + 2 ⋅ s 2 + 3 ⋅ s 3 + . . . + ( p − 1 ) ⋅ s p − 1 ) m o d     p 22222222222 22 s ⋅ f ( s , p ) = − ( 0 ⋅ s 1 + 1 ⋅ s 2 + 2 ⋅ s 3 + . . . + ( p − 2 ) ⋅ s p − 1 + ( p − 1 ) ⋅ s p ) m o d     p \phantom{} Let \phantom{2} f(s, p) = - \left( 1 \cdot s^{1} + 2 \cdot s^{2} + 3 \cdot s^{3} + ... + (p-1) \cdot s^{p-1} \right) \mod p \phantom{22222222222} \\ \phantom{22} s\cdot f(s, p) = - \left( 0 \cdot s^{1} + 1 \cdot s^{2} + 2 \cdot s^{3} + ... + (p-2) \cdot s^{p-1} + (p-1) \cdot s^{p} \right) \mod p \phantom{} L e t 2 f ( s , p ) = − ( 1 ⋅ s 1 + 2 ⋅ s 2 + 3 ⋅ s 3 + ... + ( p − 1 ) ⋅ s p − 1 ) mod p 22222222222 22 s ⋅ f ( s , p ) = − ( 0 ⋅ s 1 + 1 ⋅ s 2 + 2 ⋅ s 3 + ... + ( p − 2 ) ⋅ s p − 1 + ( p − 1 ) ⋅ s p ) mod p On subtracting the two equations, we get
( 1 − s ) ⋅ f ( s , p ) = − ( s 1 + s 2 + s 3 + . . . + s p − 1 + ( p − 1 ) ⋅ s p ) m o d     p (1-s) \cdot f(s,p) = -( s^{1}+s^{2}+s^{3}+ ...+s^{p-1}+ (p-1) \cdot s^{p} ) \mod p ( 1 − s ) ⋅ f ( s , p ) = − ( s 1 + s 2 + s 3 + ... + s p − 1 + ( p − 1 ) ⋅ s p ) mod p We now use the series formula for geometric progressions to simplify
( 1 − s ) ⋅ f ( s , p ) = − ( ( s ⋅ ( 1 − s p − 1 ) ) 1 − s + ( p − 1 ) ⋅ s p ) m o d     p (1-s) \cdot f(s,p) = -(\frac{( s \cdot (1- s^{p-1}))}{1-s }+ (p-1) \cdot s^{p} ) \mod p ( 1 − s ) ⋅ f ( s , p ) = − ( 1 − s ( s ⋅ ( 1 − s p − 1 )) ​ + ( p − 1 ) ⋅ s p ) mod p From Fermat's theorem, we get
1 − s p − 1 ≡ 0 ( m o d n ) 1 - s^{p-1} \equiv 0 \pmod n 1 − s p − 1 ≡ 0 ( mod n ) p − 1 ⋅ s p ≡ − s ( m o d p ) p-1 \cdot s^{p} \equiv -s \pmod p p − 1 ⋅ s p ≡ − s ( mod p ) Substituting into the equation, we get
f ( s , p ) = s 1 − s m o d     p f(s,p) = \frac{s}{1-s} \mod p f ( s , p ) = 1 − s s ​ mod p
Finally, we get
f ( s , p ) = A = 1 1 − s − 1 ( m o d p ) f(s,p) = A = \frac{1}{1-s} -1 \pmod p f ( s , p ) = A = 1 − s 1 ​ − 1 ( mod p ) s ≡ − ( A + 1 ) − 1 + 1 ( m o d p ) {s} \equiv -(A+1)^{-1} + 1 \pmod p s ≡ − ( A + 1 ) − 1 + 1 ( mod p ) Therefore, we can simply attain the value of s by a single line of code, after which we get the flag
Copy s= inverse(-A-1,p)+1
#FLAG{Do_the_math396691ba7d7270a}