April 20, 2007
luyuanhsiung
在天空部落發表於22:10:33 |
程式設計
鼓勵此網誌：0
RSA加密演算法是一種非對稱加密演算法,
在公鑰加密標準和電子商業中RSA被廣泛使用,
1977年由羅納德.李維斯特、阿迪.薩莫爾和倫納德.阿德曼一起提出的~
RSA演算法原理：
1.1 原理
假設我們需要將資訊從機器A傳到機器B，首先由機器B隨機確定一個Key，我們稱之為密匙private_key，將這個可KEY始終保存在機器B中而不發出來；然後，由這個private_key計算出另一個Key，我們稱之為公匙Public_key。這個Public_key的特性是幾乎不可能通過該Key計算生成它的private_key。接下來通過網路把這個Public_key傳給機器A，
機器A受到Public_key後，利用該key，將資訊加密，並把加密後的資訊通過網路發送到機器B，最後機器B利用已知的private_key，就可以解開加密資訊。
1.2 步驟
RSA演算法的安全性依賴於大數因數分解的困難性。公匙和私匙都是兩個大素數的函數。
1.2.1
首先選擇兩個大素數p、q，計算n=p*q及m=(p-1)*(q-1)
1.2.2
而後隨機選擇加密密匙Public key，要求和m互質，比如Public key=m-1;
1.2.3
利用歐幾裏德演算法計算解密密匙Private key，使Private key滿足
Public_key * Private_key≡1(mod m)
其中Public_key，n是公匙，Private key是密匙
1.2.4
加密資訊Text時，利用公式secretword=text^Public_key (mod n)得到密文secretword
1.2.5
解密時利用公式word=text^private_key(mod n)得到原文word=text.。
實作程式：
實作驗證：
請輸入質數 p：[7]
請輸入質數 q：[17]
質數的乘積，n=pq：119
小於 n 並且與 n 互質的整數，m=ψ(n)=(p-1)×(q-1)：96
請輸入一個公開鑰匙(小於 m 並與 m 互質)：[5]
gcd:1
gcd:1
gcd:1
公開鑰匙KU為：5
value: 97
value: 193
value: 289
value: 385
私有鑰匙KR為：77
請輸入明文：[19]
輸入明文為: 19
加密後密文為：66
解密後明文為：19
在公鑰加密標準和電子商業中RSA被廣泛使用,
1977年由羅納德.李維斯特、阿迪.薩莫爾和倫納德.阿德曼一起提出的~
RSA演算法原理：
1.1 原理
假設我們需要將資訊從機器A傳到機器B，首先由機器B隨機確定一個Key，我們稱之為密匙private_key，將這個可KEY始終保存在機器B中而不發出來；然後，由這個private_key計算出另一個Key，我們稱之為公匙Public_key。這個Public_key的特性是幾乎不可能通過該Key計算生成它的private_key。接下來通過網路把這個Public_key傳給機器A，
機器A受到Public_key後，利用該key，將資訊加密，並把加密後的資訊通過網路發送到機器B，最後機器B利用已知的private_key，就可以解開加密資訊。
1.2 步驟
RSA演算法的安全性依賴於大數因數分解的困難性。公匙和私匙都是兩個大素數的函數。
1.2.1
首先選擇兩個大素數p、q，計算n=p*q及m=(p-1)*(q-1)
1.2.2
而後隨機選擇加密密匙Public key，要求和m互質，比如Public key=m-1;
1.2.3
利用歐幾裏德演算法計算解密密匙Private key，使Private key滿足
Public_key * Private_key≡1(mod m)
其中Public_key，n是公匙，Private key是密匙
1.2.4
加密資訊Text時，利用公式secretword=text^Public_key (mod n)得到密文secretword
1.2.5
解密時利用公式word=text^private_key(mod n)得到原文word=text.。
實作程式：
1
import java.io.*;
2
3public class Rsa
4
{
5
private int p=0;
6 private int q=0;
7 private long n=0;
8 private long m=0;
9
10 private long public_key=0;//公匙
11 private long private_key=0;//密匙
12
13 private long text=0;//明文
14 private long secretword=0;//密文
15 private long word=0;//解密後明文
16
17 //判斷是否為質數
18 public boolean primenumber(long t)
19
{
20 long k=0;
21 k=(long)Math.sqrt((double)t);
22 boolean flag=true;
23 outer:for(int i=2;i<=k;i++)
24 {
25 if((t%i)==0)
26 {
27 flag = false;
28 break outer;
29
}
30 }
31 return flag;
32 }
33 //輸入PQ
34 public void inputPQ()throws Exception
35 {
36 do{
37 System.out.print("請輸入質數 p：");
38 BufferedReader stdin=new BufferedReader(new InputStreamReader(System.in));
39 String br=stdin.readLine();
40 this.p=Integer.parseInt(br);
41 }
42 while(!primenumber(this.p));
43 do{
44 System.out.print("請輸入質數 q：");
45 BufferedReader stdin=new BufferedReader(new InputStreamReader(System.in));
46 String br=stdin.readLine();
47 this.q=Integer.parseInt(br);
48 }
49 while(!primenumber(this.q));
50 this.n=this.p*this.q;
51 this.m=(p-1)*(q-1);
52 System.out.println("質數的乘積，n=pq："+this.n);
53 System.out.println("小於 n 並且與 n 互質的整數，m=ψ(n)=(p-1)×(q-1)："+this.m);
54 }
55 //求最大公約數
56 public long gcd(long a,long b)
57 {
58 long gcd;
59 if(b==0)
60 gcd=a;
61 else
62 gcd=gcd(b,a%b);
63 System.out.println("gcd:"+gcd);
64 return gcd;
65
66 }
67 //輸入公匙
68 public void getPublic_key()throws Exception
69 {
70 do{
71 System.out.print("請輸入一個公開鑰匙(小於 m 並與 m 互質)： ");
72 BufferedReader stdin=new BufferedReader(new InputStreamReader(System.in));
73 String br=stdin.readLine();
74 this.public_key=Long.parseLong(br);
75 }while((this.public_key >= this.m) || (this.gcd(this.m,this.public_key)!=1));
76 System.out.println("公開鑰匙KU為："+this.public_key);
77 }
78 //計算得到密匙
79 public void getPrivate_key()
80 {
81 long value=1;
82 outer:for(long i=1;;i++)
83 {
84 value=i*this.m+1;
85 System.out.println("value: "+value);
86 if((value%this.public_key==0)&& (value/this.public_key < this.m))
87 {
88 this.private_key=value/this.public_key;
89 break outer;
90 }
91 }
92 System.out.println("私有鑰匙KR為："+this.private_key);
93 }
94 //輸入明文
95 public void getText()throws Exception
96 {
97 System.out.print("請輸入明文：");
98 BufferedReader stdin=new BufferedReader(new InputStreamReader(System.in));
99 String br=stdin.readLine();
100 this.text=Long.parseLong(br);
101 }
102 //加密、解密計算
103 public long colum(long y,long n,long key)
104 {
105 long mul;
106 if(key==1)
107 mul=y%n;
108 else
109 mul=y*this.colum(y,n,key-1)%n;
110 return mul;
111 }
112
113 //加密後解密
114 public void pascolum()throws Exception
115 {
116 this.getText();
117 System.out.println("輸入明文為: "+this.text);
118 //加密
119 this.secretword=this.colum(this.text,this.n,this.public_key);
120 System.out.println("加密後密文為："+this.secretword);
121 //解密
122 this.word=this.colum(this.secretword,this.n,this.private_key);
123 System.out.println("解密後明文為："+this.word);
124
125 }
126 public static void main(String []args)throws Exception
127 {
128 Rsa t = new Rsa();
129 t.inputPQ();
130 t.getPublic_key();
131 t.getPrivate_key();
132 t.pascolum();
133 }
134
135
}
import java.io.*;2
3
public class Rsa 4
{
5
private int p=0;6
private int q=0;7
private long n=0;8
private long m=0;9
10
private long public_key=0;//公匙11
private long private_key=0;//密匙12
13
private long text=0;//明文14
private long secretword=0;//密文15
private long word=0;//解密後明文16
17
//判斷是否為質數18
public boolean primenumber(long t)19
{
20
long k=0;21
k=(long)Math.sqrt((double)t);22
boolean flag=true;23
outer:for(int i=2;i<=k;i++)24
{25
if((t%i)==0)26
{27
flag = false;28
break outer;29
}30
}31
return flag;32
}33
//輸入PQ34
public void inputPQ()throws Exception35
{36
do{37
System.out.print("請輸入質數 p：");38
BufferedReader stdin=new BufferedReader(new InputStreamReader(System.in));39
String br=stdin.readLine();40
this.p=Integer.parseInt(br);41
}42
while(!primenumber(this.p));43
do{44
System.out.print("請輸入質數 q：");45
BufferedReader stdin=new BufferedReader(new InputStreamReader(System.in));46
String br=stdin.readLine();47
this.q=Integer.parseInt(br);48
}49
while(!primenumber(this.q));50
this.n=this.p*this.q;51
this.m=(p-1)*(q-1);52
System.out.println("質數的乘積，n=pq："+this.n);53
System.out.println("小於 n 並且與 n 互質的整數，m=ψ(n)=(p-1)×(q-1)："+this.m);54
}55
//求最大公約數56
public long gcd(long a,long b)57
{58
long gcd;59
if(b==0)60
gcd=a;61
else62
gcd=gcd(b,a%b);63
System.out.println("gcd:"+gcd);64
return gcd;65
66
}67
//輸入公匙68
public void getPublic_key()throws Exception69
{70
do{71
System.out.print("請輸入一個公開鑰匙(小於 m 並與 m 互質)： ");72
BufferedReader stdin=new BufferedReader(new InputStreamReader(System.in));73
String br=stdin.readLine();74
this.public_key=Long.parseLong(br);75
}while((this.public_key >= this.m) || (this.gcd(this.m,this.public_key)!=1));76
System.out.println("公開鑰匙KU為："+this.public_key);77
}78
//計算得到密匙79
public void getPrivate_key()80
{81
long value=1;82
outer:for(long i=1;;i++)83
{84
value=i*this.m+1;85
System.out.println("value: "+value);86
if((value%this.public_key==0)&& (value/this.public_key < this.m))87
{88
this.private_key=value/this.public_key;89
break outer;90
}91
}92
System.out.println("私有鑰匙KR為："+this.private_key);93
}94
//輸入明文95
public void getText()throws Exception96
{97
System.out.print("請輸入明文：");98
BufferedReader stdin=new BufferedReader(new InputStreamReader(System.in));99
String br=stdin.readLine();100
this.text=Long.parseLong(br);101
}102
//加密、解密計算103
public long colum(long y,long n,long key)104
{105
long mul;106
if(key==1)107
mul=y%n;108
else 109
mul=y*this.colum(y,n,key-1)%n;110
return mul;111
}112
113
//加密後解密114
public void pascolum()throws Exception115
{116
this.getText();117
System.out.println("輸入明文為: "+this.text);118
//加密119
this.secretword=this.colum(this.text,this.n,this.public_key);120
System.out.println("加密後密文為："+this.secretword);121
//解密122
this.word=this.colum(this.secretword,this.n,this.private_key);123
System.out.println("解密後明文為："+this.word);124
125
}126
public static void main(String []args)throws Exception127
{128
Rsa t = new Rsa();129
t.inputPQ();130
t.getPublic_key();131
t.getPrivate_key();132
t.pascolum();133
}134
135
}實作驗證：
請輸入質數 p：[7]
請輸入質數 q：[17]
質數的乘積，n=pq：119
小於 n 並且與 n 互質的整數，m=ψ(n)=(p-1)×(q-1)：96
請輸入一個公開鑰匙(小於 m 並與 m 互質)：[5]
gcd:1
gcd:1
gcd:1
公開鑰匙KU為：5
value: 97
value: 193
value: 289
value: 385
私有鑰匙KR為：77
請輸入明文：[19]
輸入明文為: 19
加密後密文為：66
解密後明文為：19
