[Crypto]Toddler RSA xp0int Posted on Oct 28 2018 # Toddler RSA <br> 基础RSA，了解RSA私钥的生成原理即可解题。题目如下：  <br> 先不管其他，看到n,分解一下，与以往不同发现可以分解为以下四个质数： ```python p1=10390947166040840011 p2=11644261463999014129 p3=16998750717539055911 p4=17462841690525028999 ``` <br> 这下可能会让人有点一脸懵逼，以往都是求出两个质数p、q,然后根据 ed ≡ 1 (mod (p-1)(q-1)) 求出私钥d来的，弄出了四个质数是不是意味着求d的公式需要改变？ <br> 答案是肯定的。第一反应相处以上公式的应该是受之前作题的思维定势所影响的。正确的应该是以下这个公式： ed ≡ 1 (mod φ(n)) <br> 现在问题就转化为了在n=p1*p2*p3*p4的情况下，该如何求 φ(n)。 两条欧拉函数的性质： 1.若m,n互质，φ(m*n)=φ(m)*φ(n) 2.若n为质数则φ(n)=n-1 推导出在n=p1*p2*p3*p4的情况下，φ(n)=(p1-1)*(p2-1)*(p3-1)*(p4-1) <br> 故解密脚本如下： ```python import gmpy2 p1=10390947166040840011 p2=11644261463999014129 p3=16998750717539055911 p4=17462841690525028999 phi=(p1-1)*(p2-1)*(p3-1)*(p4-1) e=257 d=gmpy2.invert(e,phi) c=8475628327993429564462830126573767419742875741767715368947653567552147606198 m=hex(gmpy2.powmod(c,d,p1*p2*p3*p4))[2:] for i in range(0,len(m),2): print(chr(int(m[i:i+2],16)),end='') print('') ``` <br>  打赏还是打残，这是个问题 赏 Wechat Pay Alipay [Misc]bitcoin_base [Misc]加密了吗
没有帐号? 立即注册