首页 > 其他分享 >CTF--RSA--p-1光滑

CTF--RSA--p-1光滑

时间:2024-11-05 17:41:28浏览次数:1  
标签:get -- cdots RSA CTF num primes mod

RSA--p-1光滑

对于CTF--Crypto--RSA中的p-1光滑问题,在此记录本人的学习记录以及心得。欢迎各位师傅斧正。

前备知识:

光滑数(Smooth number):可以分解成小素数的正整数。

费马小定理

\[\begin{flalign} &(a,p)=1\Longrightarrow a^{p-1}≡1(mod\quad p)\\ &费马小定理证明:\\ &首先你要知道剩余类的概念,不知道的师傅可以去补一下。\\ &对于素数p,它的剩余类是\{0,1,2,\cdots,p-1\},不再讨论0的情况。那么对于\{a,2a,\cdots,(p-1)a\}.\\ &现证明\{a,2a,\cdots,(p-1)a\}中没有相同的元素。就可以说明\{0,a,2a,\cdots,(p-1)a\}也是p的剩余类。\\ &假设有a_i,a_j元素,a_i=a_j(1≤i,j≤p-1)\rightarrow a(i-j)≡0(mod\quad p)\rightarrow p|a(i-j)\\ &这与i,j\in\{0,1,2,\cdots,p-1\}且(a,p)=1矛盾,故\{a,2a,\cdots,(p-1)a\}中没有相同的元素.\\ &则有(p-1)!≡a^{p-1}(p-1)(mod\quad p)且(p,(p-1)!)=1\rightarrow a^{p-1}≡1(mod\quad p)& \end{flalign} \]

B-Smooth:

\[\begin{flalign} &可设p-1 = p_1p_2\cdots p_s(\forall1≤i≤s)\\ &若p_1p_2\cdots p_s两两不同,则p_1p_2\cdots p_s|B!\Longrightarrow B!=k(p - 1).因此a^{B!}≡a^{k(p-1)}≡1(mod p).\\ &假设N=pq,计算gad(a^{B!}-1,N)=p即可.& \end{flalign} \]

理论代码:

from Crypto.Util.number import *
from gmpy2 import *
a = 2   # 这个就是费马小定理中的a,我们直接取素数2即可
n = 2   # n用来计算B-Smooth中的B!
while True: # 利用循环找到满足gcd(a^{B!}-1,N) = p的情况
    a = pow(a, n, N)
    res = GCD(a-1, N)
    if res != 1 and res != N:
        q = N // res
        print("p=",res)
        print("q=",q)
        break
    n += 1

典型例题:

2024SHCTFWeek2--魔鬼的步伐

      
from Crypto.Util.number import *
from random import choice
from enc import flag

m = bytes_to_long(flag)
def get_primes(limit):
    primes = []
    is_prime = [True] * (limit + 1)
    for num in range(2, limit + 1):
        if is_prime[num]:
            primes.append(num)
            for multiple in range(num * num, limit + 1, num):
                is_prime[multiple] = False
    return primes

def get_Prime(bits):
    while True:
        n = 2
        while n.bit_length() < bits:
            n *= choice(primes)
        if isPrime(n + 1):
            return n + 1

e = 65537
primes = get_primes(e)
p = get_Prime(512)
q = get_Prime(512)
n = p*q
c = pow(m,e,n)
print(f"n = {n}")
print(f"e = {e}")
print(f"c = {c}")
'''
n = 779579301738188606639541475585479048662338414978423162511086618350581959037809676355175033940672838358216296034989613684765924879020007985463372880378958453235938149726732804842653385407460552866449233717559756619739481517089434393605029261842182116054349584175198599481092380973944251651872382058614325364639417
e = 65537
c = 547032040563518540116157223879027303340872416038133089003193905244978422560735616179910978730578423924420033057963791332760379132346877909806353927165538096867865399527460216074519919572776729647581400118345644864260152466704275743378828075020134070702051989890847762735538767329450466068109132805742740564390842
'''

Analysis:

欧拉函数φ(n): 给定一个正整数 n,欧拉函数就是求在 [1,n) 区间上,与 n互质的整数的个数。举例来说,设m = 8,则与8互质的正整数集合A={1, 3, 5, 7},此集合共有4个元素,所以 φ ( 8 ) = 4。

\[\forall n\in \mathbb{N^+},φ(n)=∣A∣,whereA=\{m|1≤m≤n,(m,n)=1\}\\ |S|表示集合S中的元素个数 \]

欧拉定理: 对任意两个正整数 a , n ,若两者互素,则:对比费马小定理,实际上就是欧拉定理的特殊情况。因为素数p的φ(p)=p-1

\[a^{φ(n)}≡1(mod\ \ n)=>a^{kφ(n)}=(a^{φ(n)})^k≡1^k≡1(mod\ \ n) \]

所以只要指数是模数n的欧拉函数的倍数,在模n下就等于1.

对于本题中的情况:

\[p = p_1p_2\cdots p_s+1;q=q_1q_2\cdots q_t+1\\ φ(p)=p_1p_2\cdots p_s;φ(q)=q_1q_2\cdots q_t\\ n = pq;φ(n)=p_1p_2\cdots p_sq_1q_2\cdots q_t\\ 所以只需要遍历get\_primes()得到的素数表就可以得到数a的计算指数.\\ 得,a^{k*φ(n)}≡1(mod\ \ n)\\ a^{k*φ(n)}-1≡0(mod\ \ p)=>gcd(a^{k*φ(n)}-1,n)=p \]

exp:

from Crypto.Util.number import *
# Given values
n = 779579301738188606639541475585479048662338414978423162511086618350581959037809676355175033940672838358216296034989613684765924879020007985463372880378958453235938149726732804842653385407460552866449233717559756619739481517089434393605029261842182116054349584175198599481092380973944251651872382058614325364639417
e = 65537
c = 547032040563518540116157223879027303340872416038133089003193905244978422560735616179910978730578423924420033057963791332760379132346877909806353927165538096867865399527460216074519919572776729647581400118345644864260152466704275743378828075020134070702051989890847762735538767329450466068109132805742740564390842

# 初始化生成光滑数的列表get_primes(e)
def get_primes(limit):
    primes = []
    is_prime = [True] * (limit + 1)
    for num in range(2, limit + 1):
        if is_prime[num]:
            primes.append(num)
            for multiple in range(num * num, limit + 1, num):
                is_prime[multiple] = False
    return primes
# 由于n = p * q ,而p,q分别由一个get_primes生成,所以最终n的列表应该是2*get_primes(e)
primes_value = get_primes(e) + get_primes(e)

# 求解φ(n)
def Solve(n):
    counter = 0
    for p in primes_value:
        if n % p == 0:
            counter += 1
    return n - counter - 2  # 减去1和n的两种情况
# 取素数2当作最初的a,在φ(n)的范围内不断增大指数寻找GCD(a^{k*φ(n)}-1,n) != 0和 != n
a = 2
for _ in range(2,Solve(n)):
    a = pow(a,_,n)
    p = GCD(a-1,n)
    if p !=1 and p != n:
        q = n // p
        break
phi_n = (p-1)*(q-1)
d = inverse(e,phi_n)
flag = long_to_bytes(pow(c,d,n))
print(flag)
#SHCTF{1rlCTioN_is_ThE_d3vils_st3P_4s}

写在最后:

例题不多,但是我觉得这道题的质量足以锻炼RSA中p-1光滑的题型的考点以及应对策略,我们的最终目的就是寻找到φ(n),之后取a=2利用费马小定理或者欧拉定理进行求解得到a^{φ(n)}≡1(mod p) => gcd(n,a^{φ(n)}-1) = p,判断条件就是gcd(n,a^{φ(n)}-1) !=1 and gcd(n,a^{φ(n)}-1) != n.

标签:get,--,cdots,RSA,CTF,num,primes,mod
From: https://www.cnblogs.com/chen-xing-zzu/p/18528441

相关文章

  • 力扣新手村之1342、1672、412
    1342[将数字变成0的操作次数]题目链接LeetCode1342[将数字变成0的操作次数]详情实例实例1实例2实例3提示题解思路判断num是否为0不为0则判断num是否为偶数num是偶数则除以2num不是偶数则减1操作次数加1重复上述步骤,直到num为0,返回操作次数代码cla......
  • 国内首位聋人 Android 软件工程师体验通义灵码,“这真是太棒了”
    Hi大家好!我就是人见人爱、Bug闪开的通义灵码!上个月,我上线了一项新能力:体验通义灵码@workspace:轻松分析项目结构,结合代码仓库理解工程、查询问答等补充说明:当你需要快速了解一个工程、查找工程内的实现逻辑,或有新的诉求需要进行代码变更时,可以在智能问答窗口中通过 @ 可......
  • 诛仙3:幻心千劫|单机安装教程|虚拟机一键端|GM工具包
    天给大家带来一款单机游戏的架设:诛仙3-幻心千劫-16职业。游戏版本:v4.4.0只适用于单机娱乐,此教程是本人亲测所写,踩坑无数,如果你是小白跟着教程走也是可以搭建  亲测视频演示https://githubs.xyz/show/297.mp4 游戏安装步骤此游戏架设需要安装虚拟机,没......
  • Pandas读写数据库
    python库要求pandas提供读写关系型数据库的函数和方法SQLAlchemy配合相应数据库的Python连接工具pymysqlmysql数据库Python连接工具安装数据库下载地址:https://dev.mysql.com/downloads/安装注意事项:记住设置的root账户密码记住端口号,默认为3306创建数据库打开数......
  • 海光 DCU信息查询
     查看GPU(加速卡)查看GPU型号rocminfo|grep-izifang(zifang表示:Z100)[root@worker-0root]rocminfo|grep-izifangName:ZIFANGName:ZIFANG查看GPU使用率设备及显存占用(每次显......
  • 钢条切割
    问题描述现有一段长度为10的钢条,可以零成本将其切割为多段长度更小钢条。怎样合理切割,使总收益最大。钢条长度12345678910价格1589101717202424观察问题可以知道该问题属于区间动态规划。建立问题的递推关系,我们每次只切一刀,然后比较不切割......
  • Kubernetes架构及核心组件
    一、基本架构Kubernetes集群可以被看作是一个工厂,而各个组件则是这个工厂里的不同部门:KubernetesAPI服务器:就像是这个工厂的总经理,负责接收所有的请求并将它们分配给相应的部门进行处理。etcd:就像是这个工厂的记事本,负责记录所有的配置信息和状态信息,以便其他组件可......
  • springboot 二手书交易平台,计算机毕业设计项目源码 022,计算机毕设程序(LW+开题报告、中
    目 录摘要1绪论1.1项目开发背景1.2项目开发意义1.3springboot框架介绍1.3论文结构与章节安排2 二手书交易平台系统分析2.1可行性分析2.2系统流程分析2.2.1数据流程3.3.2业务流程2.3系统功能分析2.3.1功能性分析2.3.2非功能性分析2.4......
  • 活着就好20241105
    ......
  • 基于springboot的即动运动网站的设计与实现,计算机毕业设计项目源码 023,计算机毕设程序
    摘 要随着互联网趋势的到来,各行各业都在考虑利用互联网将自己推广出去,最好方式就是建立自己的互联网系统,并对其进行维护和管理。在现实运用中,应用软件的工作规则和开发步骤,采用Java技术建设即动运动网站。本设计主要实现集人性化、高效率、便捷等优点于一身的即动运动网......