【CTF-RSA】又是费马小定理

推理过程

费马小定理

p是素数

a^p-1%p=1

a^p%p=a%p

k1 =pow(g,a1*(p-1),n)

k1 =g^(a1*(p-1))%n

k1 =g^(a1*(p-1))+kn

#两边同时模上p

k1%p=g^(a1*(p-1))%p+kn%p

k1%p=g^(a1*(p-1))%p

k1%p=(g^a1)^(p-1)%p

#根据费马小定理

k1%p=1

k1-1=kp

#利用公约数的原理

p=gcd(k1-1,n)

q=n//p

c1 = (pow(k1,b1,n)*flag)%n

c1=(k1^b1%n*flag)%n

c1=(k1^b1%n*flag%n)%n

c1=(k1^b1*flag)%n

c1=(k1^b1*flag)+kn

#两边同时模上p

c1%p=(k1^b1*flag)%p

c1%p=(k1^b1%p*flag%p)%p

#k1%p=1

c1%p=((k1%p)^b1)%p*flag%p)%p

c1%p=(1^b1)%p*flag%p)%p

c1%p=(1*flag%p)%p

c1%p=flag%p

c1%p=flag