首页 > 其他分享 >dp泄露

dp泄露

时间:2024-10-09 16:47:49浏览次数:12  
标签:phi -- k2 k1 泄露 dp mod

一直在抄脚本,终于想着来看看原理了。

dp是什么?

  dp = d mod (p-1)

基本前备知识

  e*d = 1 mod ϕ(n)

那么开推吧

dp = d mod (p-1)

--> dp * e = e*d mod (p-1)

--> e*d = dp * e mod (p-1)

--> e*d = dp *e  + k1*(p-1)

             --> dp * e + k1*(p-1) = 1 mod ϕ(n)

              --> dp * e + k1*(p-1) = 1 + k2*ϕ(n)

                         --> dp * e + k1*(p-1) = 1 + k2*(p-1)*(q-1)

                  --> dp * e = 1 + (k2*(q-1) - k1) * (p-1)

由于

dp < (p-1)

所以

0 < (k2*(q-1) - k1) < e

对(p-1)进行爆破即可

脚本

for i in range(1,e):
    if (dp*e-1)%i==0:
        if n%(((dp*e-1)//i)+1)==0:
            p=(dp*e-1)//i+1
            q=n//p
            phi=(p-1)*(q-1)
            d=inverse(e,phi)
            m=pow(c,d,n)

​例题

[FSCTF 2023]RSA 3

附件:

from Crypto.Util.number import bytes_to_long
m=bytes_to_long(flag)
n= 12308543373374311860115195114269947739026255098864232126071500623399852788903738569949462616714391748269539072128882946132686996592089735285396762634029371785959865779256901123369306119124563405765293657606975290441243965513640680841871955014230301486214824204887945375140818283280272607903500556306646445508386218951500563603482945071727344737690804338144982687000734071274618240408238519378280819162796749148066754028700125846348589164721591354555019608871411236973606149388257533629388508942271702742078883636357856776193846813894734271905070538713351614750057245897158615891962167410053552739441195871000310777649
e= 65537
dp= 28196759050232165736649945458463681080421101473761579424309687746007021074159564720195299959516638110870101025657932732247788828322476803386736345945717104030991724584628153257976163663460034720811420324255626233108130037584679035250792445830510130682783638394418531763109219293027733347554816808577799709553
c= 1855798257044238280327042455832785889763141234883180404158555071443088630113034033050409259513632343742665544043437830959750873431928980910236398026670945184328950692568113819821699696418438157336263799808404698795433243968536256780396910914692949484556950491722527661706255009863481905590371725089587377065000354109396062360440021447607401687082247775453369117424848927386857425051097931983703966253652921113920387008048024308793686643944404541941182997963873579988680965558581885273185721576668001462817150245955628293258512024323515581063235248627223179117549540541642185815489978089367061102920114395871329023208

思路:

dp泄露,脚本解即可

exp:

from Crypto.Util.number import *

n= 12308543373374311860115195114269947739026255098864232126071500623399852788903738569949462616714391748269539072128882946132686996592089735285396762634029371785959865779256901123369306119124563405765293657606975290441243965513640680841871955014230301486214824204887945375140818283280272607903500556306646445508386218951500563603482945071727344737690804338144982687000734071274618240408238519378280819162796749148066754028700125846348589164721591354555019608871411236973606149388257533629388508942271702742078883636357856776193846813894734271905070538713351614750057245897158615891962167410053552739441195871000310777649
e= 65537
dp= 28196759050232165736649945458463681080421101473761579424309687746007021074159564720195299959516638110870101025657932732247788828322476803386736345945717104030991724584628153257976163663460034720811420324255626233108130037584679035250792445830510130682783638394418531763109219293027733347554816808577799709553
c= 1855798257044238280327042455832785889763141234883180404158555071443088630113034033050409259513632343742665544043437830959750873431928980910236398026670945184328950692568113819821699696418438157336263799808404698795433243968536256780396910914692949484556950491722527661706255009863481905590371725089587377065000354109396062360440021447607401687082247775453369117424848927386857425051097931983703966253652921113920387008048024308793686643944404541941182997963873579988680965558581885273185721576668001462817150245955628293258512024323515581063235248627223179117549540541642185815489978089367061102920114395871329023208

for i in range(1,e):
    if (dp*e-1)%i==0:
        if n%(((dp*e-1)//i)+1)==0:
            p=(dp*e-1)//i+1
            q=n//p
            phi=(p-1)*(q-1)
            d=inverse(e,phi)
            m=pow(c,d,n)
            print(long_to_bytes(m))

标签:phi,--,k2,k1,泄露,dp,mod
From: https://www.cnblogs.com/snoozy/p/18454596

相关文章

  • (LeetCode 热题 100) 1143. 最长公共子序列(动态规划dp)
    题目:1143.最长公共子序列思路:经典动态规划dp题型,时间复杂度为0(n^2)。C++版本:classSolution{public:intlongestCommonSubsequence(stringtext1,stringtext2){intn=text1.size(),m=text2.size();//状态f[i][j]表示:text1[0,i]和text2[0......
  • pgadmin4敏感信息泄露 CVE-2024-9014
    0x01产品描述:        pgAdmin是全球最先进的开源数据库Postgres的领先开源管理工具。 pgAdmin4旨在满足新手和经验丰富的Postgres用户的需求,提供了强大的图形界面,可简化数据库对象的创建,维护和使用。其可以在Linux,Unix,macOS和Windows上使用,以管理PostgreSQL和EDBA......
  • 液体泄露检测系统 监控识别管道液体泄漏系统
    液体泄露检测系统通过在关键区域安装监控摄像头,液体泄露检测系统对管道的液体泄露情况进行全天候不间断实时监测。液体泄露检测系统利用Ai视觉智能分析技术,实时感知监控画面中管道液体泄露事件。液体泄露检测系统检测到画面中管道设备液体泄露现象时,将自动发出警报提示相关人员及......
  • 前端的全栈混合之路Meteor篇:分布式数据协议DDP深度剖析
    本文属于进阶篇,并不是太适合新人阅读,但纯粹的学习还是可以的,因为后续会实现很多个ddp的版本用于web端、nodejs端、安卓端和ios端,提前预习和复习下。ddp协议是一个C/S架构的协议,但是客户端也同时可以是服务端。什么是DDP?DDP(DistributedDataProtocol)是Meteor框架中......