最近学习rsa涨了不少新知识,这次遇到了一个比较简单但是需要想想的题目,因为发现网上没有查到wp就想写一下提供一些思路。

首先题目给了n,p-q,e,然后n很大,无法使用工具分解,呢么感觉肯定是利用p-q这个点求d了

n=24585768801100871989460458412563674690545986652089097718040761783186739174559136657307807040444318337561194142282186006216583089898423180103199568738639814413601595196467099996734334212909157604318709957690532885862891927163713619932622153281344607898846228206181834468325246573910857887714824338949742479585089251882243488454602710292507668577598274622372304293403731722318890268908300308478539449464617438721833942643889296634768118375076052778833640986893990732882252524850152650060780854621796349622086656401914022236044924841914313726991826438982902866584892213702893596657746111940812657202364588469026832387629

p-q=

14048479366496281701869293063643750801596179514889914988732592464154208813942939793532694949932787548745769133200541469022315588864587160064703369956054828780928008235304461825448872454098086255531582368864754318040219023548966787642948010656526691472780392631956031751285174567712974691729142190835749586660

e = 65537

c = 13043206753625359891696429504613068427529111016070088678736297291041435652992434742862062899975037273524389833567258051170507686131853178642412748377655159798601888072877427570380109085131089494464136940524560062629558966202744902709909907514127527274581612606840291391818050072220256661680141666883565331886278443012064173917218991474525642412407692187407537171479651983318468186723172013439034765279464665108704671733067907815695414348312753594497823099115037082352616886076617491904991917443093071262488786475411319592529466108485884029307606114810451140886975584959872328937471166255190940884805476899976523580343

呢么这里就用到了一些关于初中数学的小知识,d=(p-1)(q-1)=pq-(p+q)+1

呢么n=pq已经知道了,在求出来p+q就行了。呢么如何求p+q呢?这里肯定要放眼到p-q的,首先(p-q)(p-q)=p*p+q*q-2n然后(p+q)(p+q)=p*p+q*q+2n,也就是说能求出来y=p+q

求p+q:

import math
import gmpy2
n=24585768801100871989460458412563674690545986652089097718040761783186739174559136657307807040444318337561194142282186006216583089898423180103199568738639814413601595196467099996734334212909157604318709957690532885862891927163713619932622153281344607898846228206181834468325246573910857887714824338949742479585089251882243488454602710292507668577598274622372304293403731722318890268908300308478539449464617438721833942643889296634768118375076052778833640986893990732882252524850152650060780854621796349622086656401914022236044924841914313726991826438982902866584892213702893596657746111940812657202364588469026832387629
x=14048479366496281701869293063643750801596179514889914988732592464154208813942939793532694949932787548745769133200541469022315588864587160064703369956054828780928008235304461825448872454098086255531582368864754318040219023548966787642948010656526691472780392631956031751285174567712974691729142190835749586660
y=x*x
z=y+4*n
q=gmpy2.isqrt(z)
print q

求出p+q来就得到flag了
#!/usr/bin/python
#coding:utf-8

import libnum
from Crypto.Util.number import long_to_bytes

x = 24585768801100871989460458412563674690545986652089097718040761783186739174559136657307807040444318337561194142282186006216583089898423180103199568738639814413601595196467099996734334212909157604318709957690532885862891927163713619932622153281344607898846228206181834468325246573910857887714824338949742479585089251882243488454602710292507668577598274622372304293403731722318890268908300308478539449464617438721833942643889296634768118375076052778833640986893990732882252524850152650060780854621796349622086656401914022236044924841914313726991826438982902866584892213702893596657746111940812657202364588469026832387629
y = 313911508194450175570632595955672449806614397067433716077861356318241639602539415146427164747918893278353408869473491895193527215277755282703791989765796626512243061215408359221962662362641939950515512881269464358321542098202690113744333540601483874730634934587010409040497502224033520896973739974013262725454
c = 13043206753625359891696429504613068427529111016070088678736297291041435652992434742862062899975037273524389833567258051170507686131853178642412748377655159798601888072877427570380109085131089494464136940524560062629558966202744902709909907514127527274581612606840291391818050072220256661680141666883565331886278443012064173917218991474525642412407692187407537171479651983318468186723172013439034765279464665108704671733067907815695414348312753594497823099115037082352616886076617491904991917443093071262488786475411319592529466108485884029307606114810451140886975584959872328937471166255190940884805476899976523580343
e = 65537
n = x
phi = n-y+1

d = libnum.invmod(e,phi)
m = pow(c,d,n)
print long_to_bytes(m)

最新文章

  1. 2015.4.20 Canvas Jquery 移动端 JavaScript
  2. poj2762 缩点+topo排序
  3. 【FFmpeg】ffplay播放rtsp视频流花屏问题
  4. asp.net发布webservice出现‘Could not write to output file ‘解决办法
  5. TC SRM 607 DIV2
  6. 你所不知道的string.xml
  7. 建立qemu桥接的网络连接
  8. .Net 4.5中的HttpClient试用
  9. sublime3安装
  10. jqery 图片等 比例缩放
  11. 记录下Webapi签名机制
  12. 【html5】html5离线存储
  13. spring官网上下载历史版本的spring插件,springsource-tool-suite
  14. Daily Scrumming* 2015.12.22(Day 14)
  15. [转]对form:input标签中的数字进行格式化
  16. Uva 11520 - Fill the Square 贪心 难度: 0
  17. video兼容--可用
  18. mysql的mysqli异步与php的携程
  19. hibernate+pageBean实现分页dao层功能代码
  20. python函数、装饰器、迭代器、生成器

热门文章

  1. MySQL 日志之 binlog 格式 → 关于 MySQL 默认隔离级别的探讨
  2. Laravel使用Ajax提交表单报419 unknown status错误的解决方法
  3. spring3.X版本知识点
  4. 10 张图打开 CPU 缓存一致性的大门
  5. jq animate 的第二写法
  6. oracle 查询数据库锁及锁处理
  7. for循环中的let与var的说明
  8. 【实验课选题详解】用C语言实现万年历
  9. C# 实现十六进制Unicode编码字符串转换为汉字
  10. 如何在 Debian 9 上搭建 LNMP 环境