大數的質因數分解為什麼會破解密碼？

1樓：viness

RAS的加密原理大概是這樣的。先選擇兩個大的質數p和q，然後自然的有n=p*q，有了這個前提之後我們開始生成公鑰和秘鑰。

1、公鑰的選取方式是這樣的：

a.首先計算（這個東西是尤拉函式，大概的意思就是說比n小的正整數裡面和n互質的數有多少個）。根據尤拉函式的性質有 :

上述公示成立的前提呢就是p和q都是質數。

b.選取乙個數e，而且要滿足 ,說人話呢就是e和的最大公約數要為1，也就是要互質

通過上述a、b步驟我們就得到了公鑰。

2、私鑰的選取方式是這樣的：

設私鑰為d，d需要滿足 ,說人話就是私鑰d和公鑰e的乘積和的模要為1。知道了e和可以通過計算得到d，計算方法為：

其中k為整數

3、加密方式是這樣的：

設明文為m，秘文為c的話，

這是加密步驟，通過e和n可以完成加密

這是解密步驟，通過d和n可以完成解密

通過上述描述不難看出公鑰為e和n，秘鑰為d和n。如果我們想通過公鑰推算出秘鑰的話，由於根據上文，那我們就需要知道。根據尤拉公式的通式：

(其中p1, p2……pi為n的所有質因數，k是不為0的整數)

這就需要將n這個大數進行質因數分解，得到n的所有質因數進而計算出 ,最終得到秘鑰d。當然也可以手動計算比n小的正整數裡面有多少個數和n互質也可以得到的值

2樓：王國欽

加密演算法設計的目的是在保證正常加解密運算適合當前運算能力發展的前提下，盡可能地讓破解（暴力破解或其它破解手段）變得複雜困難。由於破解難度通常隨加解密難度增加而（呈指數形式）增長，因此通過用數學定理來證明加密演算法的安全性，可以有效防止演算法被從其它方面攻破，保證演算法總體的有效性。

而在數學世界中，往往形式簡單的定理更為牢靠。目前密碼學領域最常用的是基於以下兩個數學定理：

（1）大數的質因數分解。通常證明兩個更小的數為質數更容易，而要分解這兩個質數的乘積，難度呈指數增長。加密演算法生成兩個質數並保密，使用其乘積來參與加解密；破解時需要分解乘積得到兩個原質數，難度比生成金鑰和加解密時要難得多得多。

代表性的演算法為RSA。本題所述的也是這類演算法。

（2）橢圓曲線演算法。在已知橢圓曲線上選取乙個點並保密，通過尋找過這一點的一條切線，得到切線與橢圓曲線的另一交點 K = kG。使用K來參與加解密；破解時需要分解得到原始的G。

（貌似這裡還是乙個大數分解的問題，但我不是很確定）

這裡主要是一系列基於ECC的加解密和簽名演算法。