Python如何引用歐拉常數(shù)

歐拉常數(shù)(Euler-Mascheroniconstant)。

目前創(chuàng)新互聯(lián)建站已為近千家的企業(yè)提供了網(wǎng)站建設(shè)、域名、網(wǎng)頁(yè)空間、網(wǎng)站改版維護(hù)、企業(yè)網(wǎng)站設(shè)計(jì)、潮安網(wǎng)站維護(hù)等服務(wù)，公司將堅(jiān)持客戶導(dǎo)向、應(yīng)用為本的策略，正道將秉承"和諧、參與、激情"的文化，與客戶和合作伙伴齊心協(xié)力一起成長(zhǎng)，共同發(fā)展。

學(xué)過(guò)高等數(shù)學(xué)的人都知道，調(diào)和級(jí)數(shù)S=1+1/2+1/3+..是發(fā)散的這時(shí)引用歐拉常數(shù)。

在數(shù)論，對(duì)正整數(shù)n，歐拉函數(shù)是小于n的正整數(shù)中與n互質(zhì)的數(shù)的數(shù)目（因此φ(1)=1）此函數(shù)以其首名研究者歐拉命名(Euler’stotientfunction)，它又稱為Euler’stotientfunction、φ函數(shù)、歐拉商數(shù)等例如φ(8)=4，因?yàn)?，3，5，7均和8互質(zhì)。

python怎么調(diào)用歐拉距離的函數(shù)

φ函數(shù)的值 通式：φ(x)=x(1-1/p1)(1-1/p2)(1-1/p3)(1-1/p4)…..(1-1/pn),其中p1, p2……pn為x的所有質(zhì)因數(shù)，x是不為0的整數(shù)。φ(1)=1（唯一和1互質(zhì)的數(shù)(小于等于1)就是1本身）。 (注意：每種質(zhì)因數(shù)只一個(gè)。比如12=2*2*3那么φ

CTF常見RSA相關(guān)問(wèn)題的解決（復(fù)現(xiàn)）

本文參考 為對(duì)其知識(shí)進(jìn)行掌握，寫此文章來(lái)梳理和加深記憶

前言：理解基本概念，本文將每種攻擊方式實(shí)現(xiàn)方法提煉成了一個(gè)函數(shù)，便于理解原理也可以直接調(diào)用。

基礎(chǔ)：

RSA概要：

在開始前可以通過(guò) 《RSA算法詳解》 這篇文章了解關(guān)于RSA的基礎(chǔ)知識(shí)，包括加解密方法，算法原理和可行性證明等。（特詳細(xì)）

應(yīng)用流程：

1.選取兩個(gè)較大的互不相等的質(zhì)數(shù)p和q 計(jì)算n =p q。

2.計(jì)算phi =（p-1） （q-1）。

3.選取任意的e，使得e滿足1ephi 且 gcd(e,phi) ==1 .

4.計(jì)算e關(guān)于phi的模逆元d，即d滿足（e*d）%phi ==1.

5.加解密：c=(m^e)%n ,m =(c^d)%n.其中m為明文，c為密文 （n,e）為公鑰，d為私鑰，要求0=mn.

求模逆可直接利用gmpy2庫(kù)。如 import gmpy2 print gmpy2.invert(47,30) 可求得47模30的逆為23。

擴(kuò)展歐幾里得算法基于歐幾里得算法，能夠求出使得 ax+by=gcd(a,b) 的一組x,y。

常見攻擊方式實(shí)踐

準(zhǔn)備工具

python gmpy2庫(kù) libnum庫(kù)

yafu

RSATool2v17.exe

RSA解密

若已知私鑰d，則可以直接解密：m=pow(c,d,n).

若已知質(zhì)數(shù)p和q,則通過(guò)依次計(jì)算歐拉函數(shù)值phi、私鑰d可解密。簡(jiǎn)易實(shí)現(xiàn)如下：

在選取加密指數(shù)e時(shí)要求phi，e互質(zhì)，也就是gcd(phi,e)==1 ，如果不滿足是無(wú)法直接解密的。

SCTF2018的Crypto - a number problem，題目是： x**33=1926041757553905692219721422025224638913707 mod 3436415358139016629092568198745009225773259 tell me the smallest answer of x

其中n=3436415358139016629092568198745009225773259 可以直接分解得到p,q，出phi=(p-1)*(q-1) ，然后驚奇地發(fā)現(xiàn)gcd(phi,33)==3 。這時(shí)如果對(duì)加密過(guò)程比較熟悉的話，就可以想到實(shí)際上公鑰e=11 ，明文是m=x^3 ，應(yīng)該先求出m。然后再爆破x。

n2，n3已知，利用共模攻擊得到n1，由gcd(n1,n2)==p1 分解n1，n2，就可解密得到兩部分msg，拼接即可。

小明文攻擊

適用情況：e較小，一般為3。

公鑰e很小，明文m也不大的話，于是 m^e=k*n+m 中的的k值很小甚至為0，爆破k或直接開三次方即可。Python實(shí)現(xiàn)：

例子：Extremely hard RSA

題目提供的n是4096位的，e=3。

Rabin加密中的N可被分解

適用情況：e==2

Rabin加密是RSA的衍生算法，e==2是Rabin加密典型特征，可以百度或閱讀 以了解到詳細(xì)的說(shuō)明，這里只關(guān)注解密方法。一般先通過(guò)其他方法分解得到p，q，然后解密。

Python實(shí)現(xiàn)：

函數(shù)返回四個(gè)數(shù)，這其中只有一個(gè)是我們想要的明文，需要通過(guò)其他方式驗(yàn)證，當(dāng)然CTF中顯然就是flag字眼了。

Wiener’s Attack

適用情況：e過(guò)大或過(guò)小。

工具：

在e過(guò)大或過(guò)小的情況下，可使用算法從e中快速推斷出d的值。詳細(xì)的算法原理可以閱讀： 低解密指數(shù)攻擊 。

例子：2018強(qiáng)網(wǎng)杯nextrsa-Level2

**私鑰文件修復(fù)

適用情況：提供破損的私鑰文件。 **

參考 修復(fù)存儲(chǔ)私鑰的文件，得到p和q。

**私鑰修復(fù)

Python 腳本：**

從缺失的私鑰中，我們可以分析出各部分?jǐn)?shù)據(jù)代表的數(shù)字。

改動(dòng)原腳本中的各部分內(nèi)容即可恢復(fù)出私鑰，大致算法為：

**LSB Oracle Attack

適用情況：可以選擇密文并泄露最低位。 **

在一次RSA加密中，明文為m，模數(shù)為n，加密指數(shù)為e，密文為c。我們可以構(gòu)造出 c'=((2^e)*c)%n=((2^e)*(m^e))%n=((2*m)^e)%n ， 因?yàn)閙的兩倍可能大于n，所以經(jīng)過(guò)解密得到的明文是 m'=(2*m)%n 。我們還能夠知道 m' 的最低位 lsb 是1還是0。 因?yàn)閚是奇數(shù)，而 2*m 是偶數(shù)，所以如果 lsb 是0，說(shuō)明 (2*m)%n 是偶數(shù)，沒(méi)有超過(guò)n，即 mn/2.0 ，反之則 mn/2.0 。舉個(gè)例子就能明白 2%3=2 是偶數(shù)，而 4%3=1 是奇數(shù)。以此類推，構(gòu)造密文 c"=(4^e)*c)%n 使其解密后為 m"=(4*m)%n ，判斷 m" 的奇偶性可以知道 m 和 n/4 的大小關(guān)系。所以我們就有了一個(gè)二分算法，可以在對(duì)數(shù)時(shí)間內(nèi)將m的范圍逼近到一個(gè)足夠狹窄的空間。

更多信息可參考： RSA Least-Significant-Bit Oracle Attack 和 RSA least significant bit oracle attack 。

Python實(shí)現(xiàn)：