P14.n 是 p 的 r 次方

约 50 个字 47 行代码预计阅读时间 1 分钟

P14.n 是 p 的 r 次方

ctf 中，遇到过这样的题目：

n = p^r ，p为素数，没有q了。因为p=q。

那么计算 n 的欧拉函数 φ(n) 就是

φ(n)=p^r-p^{r-1}

推导过程为：

欧拉函数φ(n)的定义是小于n的自然数中与n互质的数的个数。

p^r 质因数就只有p，那么不与它互质的数都含有p，

和它不互质的数的个数：p^r/p=p^r-1/p=p^{r-1} 

剩下就是互质的数，其个数就是：p^r-p^{r-1} 

则有 φ(n)=p^r-p^{r-1}

出题脚本

随机生成 flag

import random
import hashlib
import string

#字符串列表
a=string.printable
#随机生成flag
for i in range(10):
    flag = ""
    for i in range(10):
        flag += a[random.randint(0, 99)]
    flag = hashlib.md5(flag.encode()).hexdigest()
    print("flag{" + flag + "}")

题目

import libnum

#生成随机素数
p=libnum.generate_prime(1024)
e=65537
m="flag{de8c3ea714f7f780185924d473997bcb}"
#字符串转数字
m=libnum.s2n(m)
n=p**4
phi_n=p**4-p**3
#求逆元
d=libnum.invmod(e,phi_n)
c=pow(m,e,n)

print ("n=",n)
print ("e=",e)
print ("c=",c)

解密脚本

import libnum
import gmpy2

n= 
e= 
c= 
#分解n
#yafu-x64.exe  factor()
p= 
phi_n=p**4-p**3
#求逆元
d=libnum.invmod(e,phi_n)
m=pow(c,d,n)
print(m)
#数字转字节，转字符串
print(libnum.n2s(int(m)).decode())