Applying Fermat’s Little Theorem in RSA challenge

Hi all, few days ago I got stuck in some RSA CTF challenge which we need to apply fermat’s little theorem to solve.
I’m going to explain with a custom challenge from Ashutosh Ahelleya. Thanks for usefull repo. More details here: link. This repo helps me improve my knowledge on RSA and number theory and I think it is suitable for such a beginner at cryptography as me.

Problem: link

We are given n,c,e and weird s :( and this is how s formed

And of course we need to focus on this one, because I try factoring n but no results

For a while I do some google and know I need to understand Fermat’s Little Theorem to solve it :>

with condition: gcd(a,p) == 1

This means: pow(a,p)-a % p == 0
=> pow(a,p)-a == kp
from here if we can find kp, just take gcd(n,kp) and we got p => solved

Proofs:

1. we have: s = pow(2,p-0xdeadbeef,n), let const = 0xdeadbeef
2. we need to find pow(2,p)
3. s = pow(2,p-const,n) => s = k*n + pow(2,p-const)

<=> pow(2,const)*s = pow(2,const)*( k*n + pow(2,p-const) )

<=> pow(2,const)*s = k*n*pow(2,const) + pow(2,const)*pow(2,p-const)

<=> pow(2,const)*s = k*p*q*pow(2,const) + pow(2,p)

if we take mod p we have:

(pow(2,const)*s )mod p = ( k*p*q*pow(2,const) + pow(2,p) ) mod p

<=> ( pow(2,const)*s ) mod p = 0 + pow(2,p,p)

Applying Fermat’s Little Theorem we have:

pow(2,p,p) => pow(2,p,p) = 2 + kp => pow(2,p,p)-2 = kp

=> (pow(2,const)*s)-2 = kp

Final step: we calculate gcd(kp,n) to find p

And Capture the flag
If you want to practice more, see RSAbaby (Codegate-CTF-Preliminary)

Sory for not beautifying the math formular. Hope you understand this one, and have a nice day