密碼如何生成素數

❶ 質數是怎樣被用於信息加密的呢

是因為質數只能被一以及自身整除，加密的話有很多種不同的組成元素，將一個大合數分為兩個質數的積非常困難，拿計算機運算的話也需要幾年的時間。所以安保系數特別高。

❷ 如何快速產生大素數 信息安全數學基礎

用密碼庫軟體快速生成大素數，像openssl，crypto++之類

❸ 如何用VC++隨機生成一個大素數（滿足RSA演算法）

你需要的包含在這個程序中，生成一個大數然後做RM素數測試，通過的我們假設其為素數即可！

RSA演算法
1978年就出現了這種演算法，它是第一個既能用於數據加密也能用於數字簽名的演算法。它易於理解和操作，也很流行。演算法的名字以發明者的名字命名：Ron Rivest, AdiShamir 和Leonard Adleman。但RSA的安全性一直未能得到理論上的證明。
RSA的安全性依賴於大數難於分解這一特點。公鑰和私鑰都是兩個大素數（大於100個十進制位）的函數。據猜測，從一個密鑰和密文推斷出明文的難度等同於分解兩個大素數的積。
密鑰對的產生。選擇兩個大素數，p 和q 。計算：n = p * q 然後隨機選擇加密密鑰e，要求 e 和 ( p - 1 ) * ( q - 1 )互質。最後，利用Euclid 演算法計算解密密鑰d, 滿足e * d = 1 ( mod ( p - 1 ) * ( q - 1 ) )其中n和d也要互質。數e和n是公鑰，d是私鑰。兩個素數p和q不再需要，應該丟棄，不要讓任何人知道。加密信息 m（二進製表示）時，首先把m分成等長數據塊 m1 ,m2,..., mi ，塊長s，其中 2^s <= n, s 盡可能的大。對應的密文是：ci = mi^e ( mod n ) ( a ) 解密時作如下計算：mi = ci^d ( mod n ) ( b )
RSA 可用於數字簽名，方案是用 ( a ) 式簽名， ( b )式驗證。具體操作時考慮到安全性和 m信息量較大等因素，一般是先作HASH 運算。RSA 的安全性。RSA的安全性依賴於大數分解，但是否等同於大數分解一直未能得到理論上的證明，因為沒有證明破解RSA就一定需要作大數分解。假設存在一種無須分解大數的演算法，那它肯定可以修改成為大數分解演算法。目前，RSA的一些變種演算法已被證明等價於大數分解。不管怎樣，分解n是最顯然的攻擊方法。現在，人們已能分解140多個十進制位的大素數。因此，模數n必須選大一些，因具體適用情況而定。
由於進行的都是大數計算，使得RSA最快的情況也比DES慢上100倍，無論是軟體還是硬體實現。速度一直是RSA的缺陷。一般來說只用於少量數據加密。
*/
#include <iostream>
#include <stdlib.h>
#include <time.h>
using namespace std;//RSA演算法所需參數
typedef struct RSA_PARAM_Tag
{
unsigned __int64 p, q; //兩個素數，不參與加密解密運算
unsigned __int64 f; //f=(p-1)*(q-1)，不參與加密解密運算
unsigned __int64 n, e; //公匙，n=p*q，gcd(e,f)=1
unsigned __int64 d; //私匙，e*d=1 (mod f)，gcd(n,d)=1
unsigned __int64 s; //塊長，滿足2^s<=n的最大的s，即log2(n)
} RSA_PARAM;//小素數表
const static long g_PrimeTable[]=
{
3,
5,
7,
11,
13,
17,
19,
23,
29,
31,
37,
41,
43,
47,
53,
59,
61,
67,
71,
73,
79,
83,
89,
97
};
const static long g_PrimeCount=sizeof(g_PrimeTable) / sizeof(long);const unsigned __int64 multiplier=12747293821;
const unsigned __int64 adder=1343545677842234541;//隨機數類
class RandNumber
{

private:
unsigned __int64 randSeed;
public:
RandNumber(unsigned __int64 s=0);
unsigned __int64 Random(unsigned __int64 n);
};
RandNumber::RandNumber(unsigned __int64 s)
{
if(!s)
{
randSeed= (unsigned __int64)time(NULL);
}
else
{
randSeed=s;
}
}
unsigned __int64 RandNumber::Random(unsigned __int64 n)
{
randSeed=multiplier * randSeed + adder;
return randSeed % n;
}static RandNumber g_Rnd;
inline unsigned __int64 MulMod(unsigned __int64 a, unsigned __int64 b, unsigned __int64 n)
{
return a * b % n;
}
unsigned __int64 PowMod(unsigned __int64 &base, unsigned __int64 &pow, unsigned __int64 &n)
{
unsigned __int64 a=base, b=pow, c=1;
while(b)
{
while(!(b & 1))
{
b>>=1; //a=a * a % n; //函數看起來可以處理64位的整數，但由於這里a*a在a>=2^32時已經造成了溢出，因此實際處理范圍沒有64位
a=MulMod(a, a, n);
} b--; //c=a * c % n; //這里也會溢出，若把64位整數拆為兩個32位整數不知是否可以解決這個問題。
c=MulMod(a, c, n);
} return c;
}
long RabinMillerKnl(unsigned __int64 &n)
{
unsigned __int64 b, m, j, v, i;
m=n - 1;
j=0; //0、先計算出m、j，使得n-1=m*2^j，其中m是正奇數，j是非負整數
while(!(m & 1))
{
++j;
m>>=1;
} //1、隨機取一個b，2<=b<n-1
b=2 + g_Rnd.Random(n - 3); //2、計算v=b^m mod n
v=PowMod(b, m, n); //3、如果v==1，通過測試
if(v == 1)
{
return 1;
} //4、令i=1
i=1; //5、如果v=n-1，通過測試
while(v != n - 1)
{
//6、如果i==l，非素數，結束
if(i == j)
{
return 0;
} //7、v=v^2 mod n，i=i+1
unsigned __int64 tmp1 = 2;
v=PowMod(v,tmp1, n);
++i; //8、循環到5
} return 1;
}
long RabinMiller(unsigned __int64 &n, long loop)
{
//先用小素數篩選一次，提高效率
for(long i=0; i < g_PrimeCount; i++)
{
if(n % g_PrimeTable[i] == 0)
{
return 0;
}
} //循環調用Rabin-Miller測試loop次，使得非素數通過測試的概率降為(1/4)^loop
for(long i=0; i < loop; i++)
{
if(!RabinMillerKnl(n))
{
return 0;
}
} return 1;
}
unsigned __int64 RandomPrime(char bits)
{
unsigned __int64 base;
do
{
base= (unsigned long)1 << (bits - 1); //保證最高位是1
base+=g_Rnd.Random(base); //再加上一個隨機數
base|=1; //保證最低位是1，即保證是奇數
} while(!RabinMiller(base, 30)); //進行拉賓－米勒測試30次
return base; //全部通過認為是素數
}
unsigned __int64 EuclidGcd(unsigned __int64 &p, unsigned __int64 &q)
{
unsigned __int64 a=p > q ? p : q;
unsigned __int64 b=p < q ? p : q;
unsigned __int64 t;
if(p == q)
{
return p; //兩數相等，最大公約數就是本身
}
else
{
while(b) //輾轉相除法，gcd(a,b)=gcd(b,a-qb)
{
a=a % b;
t=a;
a=b;
b=t;
} return a;
}
}
unsigned __int64 SteinGcd(unsigned __int64 &p, unsigned __int64 &q)
{
unsigned __int64 a=p > q ? p : q;
unsigned __int64 b=p < q ? p : q;
unsigned __int64 t, r=1;
if(p == q)
{
return p; //兩數相等，最大公約數就是本身
}
else
{
while((!(a & 1)) && (!(b & 1)))
{
r<<=1; //a、b均為偶數時，gcd(a,b)=2*gcd(a/2,b/2)
a>>=1;
b>>=1;
} if(!(a & 1))
{
t=a; //如果a為偶數，交換a，b
a=b;
b=t;
} do
{
while(!(b & 1))
{
b>>=1; //b為偶數，a為奇數時，gcd(b,a)=gcd(b/2,a)
} if(b < a)
{
t=a; //如果b小於a，交換a，b
a=b;
b=t;
} b=(b - a) >> 1; //b、a都是奇數，gcd(b,a)=gcd((b-a)/2,a)
} while(b);
return r * a;
}
}
unsigned __int64 Euclid(unsigned __int64 &a, unsigned __int64 &b)
{
unsigned __int64 m, e, i, j, x, y;
long xx, yy;
m=b;
e=a;
x=0;
y=1;
xx=1;
yy=1;
while(e)
{
i=m / e;
j=m % e;
m=e;
e=j;
j=y;
y*=i;
if(xx == yy)
{
if(x > y)
{
y=x - y;
}
else
{
y-=x;
yy=0;
}
}
else
{
y+=x;
xx=1 - xx;
yy=1 - yy;
} x=j;
} if(xx == 0)
{
x=b - x;
} return x;
}
RSA_PARAM RsaGetParam(void)
{
RSA_PARAM Rsa={ 0 };
unsigned __int64 t;
Rsa.p=RandomPrime(16); //隨機生成兩個素數
Rsa.q=RandomPrime(16);
Rsa.n=Rsa.p * Rsa.q;
Rsa.f=(Rsa.p - 1) * (Rsa.q - 1);
do
{
Rsa.e=g_Rnd.Random(65536); //小於2^16，65536=2^16
Rsa.e|=1; //保證最低位是1，即保證是奇數，因f一定是偶數，要互素，只能是奇數
} while(SteinGcd(Rsa.e, Rsa.f) != 1); Rsa.d=Euclid(Rsa.e, Rsa.f);
Rsa.s=0;
t=Rsa.n >> 1;
while(t)
{
Rsa.s++; //s=log2(n)
t>>=1;
} return Rsa;
}
void TestRM(void)
{
unsigned long k=0;
cout << " - Rabin-Miller prime check.n" << endl;
for(unsigned __int64 i=4197900001; i < 4198000000; i+=2)
{
if(RabinMiller(i, 30))
{
k++;
cout << i << endl;
}
} cout << "Total: " << k << endl;
}
void TestRSA(void)
{
RSA_PARAM r;
char pSrc[]="abcdefghijklmnopqrstuvwxyz";
const unsigned long n=sizeof(pSrc);
unsigned char *q, pDec[n];
unsigned __int64 pEnc[n];
r=RsaGetParam();
cout << "p=" << r.p << endl;
cout << "q=" << r.q << endl;
cout << "f=(p-1)*(q-1)=" << r.f << endl;
cout << "n=p*q=" << r.n << endl;
cout << "e=" << r.e << endl;
cout << "d=" << r.d << endl;
cout << "s=" << r.s << endl;
cout << "Source:" << pSrc << endl;
q= (unsigned char *)pSrc;
cout << "Encode:";
for(unsigned long i=0; i < n; i++)
{
unsigned __int64 tmp2 = q[i];
pEnc[i]=PowMod(tmp2, r.e, r.n);
cout << hex << pEnc[i] << " ";
} cout << endl;
cout << "Decode:";
for(unsigned long i=0; i < n; i++)
{
pDec[i]=PowMod(pEnc[i], r.d, r.n);
cout << hex << (unsigned long)pDec[i] << " ";
} cout << endl;
cout << (char *)pDec << endl;
}
int main(void)
{
TestRSA();
return 0;
}

❹ 急急急 求大神幫忙 用vc++ 生成1024位大素數 用到米勒拉賓素性測試

首先如果搞密碼學的編程推薦你看本書《程序員密碼學》裡面講的是現在密碼學的實現再次，解決生成大素數的這個問題思路是這樣的：隨機生成一個很大的數，用的演算法判斷這個數是不是素數如果不是繼續生成另一個大素數再判斷直到找到一個大素數也就是說核心是素性檢驗演算法這種演算法不少有fermat素性檢驗Miller-Rabin素性檢驗還有好幾種但是沒數學基礎的話是搞不懂的如果深入了解的話參照一本書《信息安全數學基礎》其中有一章都是講素性檢驗的問題的推薦樓主採用fermat素性檢驗最簡單但是個不確定演算法因為有fermat欺騙但是概率極低極低可以用/view/831881.htm

❺ C語言 設計並實現一種大素數隨機生成方法； 實現一種快速判定任意一個大數是否是素數方法 跪求啊

1. 目前來說大素數隨機生成方法是不存在的，這是一個NPC問題，NPC問題世界的七大難題之一，如果你能夠解決，就能夠拿到100萬美金的獎勵。但是現在有快速判定任意一個大數是否是素數方法：Miller Rabin演算法。

2. Miller-Rabin演算法是目前主流的基於概率的素數測試演算法，在構建密碼安全體系中佔有重要的地位。通過比較各種素數測試演算法和對Miller-Rabin演算法進行的仔細研究，證明在計算機中構建密碼安全體系時， Miller-Rain演算法是完成素數測試的最佳選擇。通過對Miller-Rabin 算 法底層運算的優化，可以取得較以往實現更好的性能。Miller-Rabin演算法是Fermat演算法的一個變形改進，它的理論基礎是由Fermat定理引申而來。
   Fermat 定理： n是一個奇素數，a是任何整數(1≤ a≤n-1) ，則 a^(n-1)≡1(mod n)。
   Miller-Rabin 演算法的理論基礎：如果n是一個奇素數， 將n-1表示成2^s*r的形式(r是奇 數)，a 是和n互素的任何整數， 那麼ar≡1(mod n) 或者對某個j(0≤j ≤s －1， j∈Z) 等式 a2jr ≡－1(mod n)成立。 這個理論是通過一個事實經由Fermat定理推導而來： n是一個奇素數，則方程x2 ≡ 1 mod n只有±1兩個解。

   
   

❻ 利用質數如何加密

質數(prime number)又稱素數，有無限個。一個大於1的自然數，除了1和它本身外，不能被其他自然數整除，換句話說就是該數除了1和它本身以外不再有其他的因數;否則稱為合數。根據算術基本定理，每一個比1大的整數，要麼本身是一個質數，要麼可以寫成一系列質數的乘積;而且如果不考慮這些質數在乘積中的順序，那麼寫出來的形式是唯一的。最小的質數是2。目前為止，人們未找到一個公式可求出所有質數。2016年1月，發現世界上迄今為止最大的素數，長達2233萬位，如果用普通字型大小將它列印出來長度將超過65公里。

❼ 質數的定義是什麼 大質數加密的原理是什麼

質數是除了1和本身之外沒有其它因數的數。有關大質數加密的原理和同餘系、矩陣有密切關系，大概是目前沒有比枚舉快很多的分解質因數的演算法。如果有興趣的話可以參看潘承洞 潘成彪的《初等數論》

❽ 為什麼素數會用在密碼學中

以前的密碼是將一個很大的數分解質因數,然後根據密碼表來獲得信息。