暗号技術 ～JAVAプログラム③～ （７週目）

Presentation on theme: "暗号技術 ～JAVAプログラム③～ （７週目）"— Presentation transcript:

1 暗号技術 ～JAVAプログラム③～ （７週目）
石川　真悟

2 RSAの暗号化処理（公開鍵暗号） 平文の値を「E」回掛け合わせ、この結果の値を「N」で割り、余りの 値を求める。この計算結果が暗号文になる。「E」と「N」は公開鍵の 値になる。 暗号文＝平文　mod N E 例）平文１２、Ｅ＝５、Ｎ＝２２１ 暗号文＝１２　mod　２２１ 暗号文＝２０７ 平文 公開鍵 ５ E N 暗号化処理 暗号文＝平文　mod N E 暗号化処理そのものは、 とてもシンプルだが、 秘密鍵の情報がわからない限り、 現実的な時間で解読するのは困難 暗号文

3 公開鍵と秘密鍵は対（ペア）になっている必要があり、この２つのキーのことをキーペアと呼 ぶ。
キーペアの生成手順 公開鍵と秘密鍵は対（ペア）になっている必要があり、この２つのキーのことをキーペアと呼 ぶ。 PとQを使ってNを計算する N=PxQ L=1cm(P-1,Q-1) P-1とQ-1の最小公倍数 PとQを使ってLを計算する 1<E<L god(E,L)=1 EとLの最大公約数が1になるEを求める Lを使ってEを計算する EとLを使ってDを計算する E x D mod L =1 EとDを掛けmodLを計算した値が 1になるようにDを求める

4 キーペアの生成の具体例 まずＰとＱの２つの素数を用意（説明を簡単にするため小さい数字で行なう） Ｐ＝１３、Ｑ＝１７
Ｎ＝ＰｘＱ＝１３ｘ１７＝２２１ Ｌ＝１ｃｍ（Ｐ－１，Ｑ－１）＝１ｃｍ（１３－１，１７－１）＝１ｃｍ（１２，１６） １２と１６の最小公倍数は４８なのでＬ＝４８ １＜Ｅ＜Ｌ　　god（Ｅ，Ｌ）＝１ God（Ｅ，４８）＝１ Ｅと４８の最大公約数が１になるようなＥを求める。 Ｅ＝5，7，11，13，17，19，23，25,29,31,35,37,41,43,47 この中から素数を１つを選ぶ。ただし、２５、３５は素数ではないので外す。 仮に５を選ぶ。 ＥｘＤ mod　Ｌ＝１ ５ｘＤ mod　４８＝１ Ｄ＝２９

5 現時点までにできているプログラムの説明 import java.io.*; //ファイルへの入出力を扱う
import java.util.*; //ファイルを読み込む class angouka1 { public static void main(String[] args) throws IOException BufferedReader br; //バッファからデータを取り出すために使うクラス System.out.println("どのくらいの素数を入力したいですか？"); br=new BufferedReader(new InputStreamReader(System.in)); String str1 = br.readLine(); int sosu; sosu = Integer.parseInt(str1); int divisor; for(int i = 2; i <= sosu; i++)

6 divisor = 0; for(int j = 1; j <= i; j++) { if(i % j == 0) divisor++; } if(divisor == 2) int y; y = sosu % i; if(y!=0) System.out.print("素数="); System.out.println(i);

7 System.out.println("上の中から2つの素数P,Qを入力してください。");
br=new BufferedReader(new InputStreamReader(System.in)); System.out.print("P="); String str2 = br.readLine(); System.out.print("Q="); String str3 = br.readLine(); System.out.println("P="+ str2 + ",Q="+ str3); int p, q, n; p = Integer.parseInt(str2); q = Integer.parseInt(str3); n = p * q; System.out.println("N="+ n); int f, m, a, b; a = p-1; b = q-1; int d=1, l; if(p>q) { f = a % b; if(f==0)

8 { l = a; System.out.println("L="+ l); } else do d++; l = a * d; f = l % b; }while(f!=0); else if(p<q) m = b % a; if(m==0)

9 { l = b; System.out.println("L="+ l); } else do d++; l = b * d; m = l % a; }while(m!=0); else if(p==q) l = a;

10 else System.out.println("エラーです。"); System.out.println("Lの値を入力してください。"); br=new BufferedReader(new InputStreamReader(System.in)); System.out.print("L="); String str4 = br.readLine(); int z; z = Integer.parseInt(str4); for(int i = 2; i <= z; i++) { divisor = 0; for(int j = 1; j <= i; j++) if(i % j == 0) divisor++; } if(divisor == 2)

11 int y; y = z % i; if(y!=0) { System.out.print("E="); System.out.println(i); } System.out.println("上のEの値から好きなEの値を1つ入力してください。"); br=new BufferedReader(new InputStreamReader(System.in)); String str5 = br.readLine(); int x; x = Integer.parseInt(str5); int angou; System.out.print("ファイル名をタイピングしてください："); String filename=br.readLine(); br=new BufferedReader(new FileReader(filename));

12 String str; int k=0; int count=0,tmp; final int bit=0x0001; char[] cary; try{ PrintWriter pw = new PrintWriter(new BufferedWriter(new FileWriter("暗号化.txt"))); while((str=br.readLine())!=null) { System.out.println(count+":"+str); cary=str.toCharArray(); System.out.print(count+":"); for(int i=0;i<cary.length;i++) int sum=0; for(int j=0;j<16;j++) tmp = cary[i]&(bit<<(15-j)); tmp >>= 15-j;

13 if(tmp==1) { System.out.print("1"); k = 16-j; } else System.out.print("0"); k = 0; sum += k; System.out.println("["+cary[i]+"] "); System.out.println("sum="+ sum +" "); angou = sum % n; //mod計算（冪乗法） for(int w = 1; w <= x-1; w++) angou *= sum; angou = angou % n;

14 if(w==x-1) { System.out.println("暗号化した文 　字の数値は"+ angou +"です。"); 　字は"+(char)angou+"です。"); pw.println(angou); } System.out.println(); count++; br.close(); pw.close(); catch(IOException e){ System.out.println("入出力エラーです。");

15 実行例

16 実行例

17

18

19

20 問題点の発見 バイナリ表示をしてkで足し算をしてsumを 計算していたが sumの値で複数の解が得られるため
(例) sum=30だった場合、 30= という解や 30= という解が得られる

21 import java.io.*; //ファイルへの入出力を扱う
import java.util.*; //ファイルを読み込む class angouka { public static void main(String[] args) throws IOException BufferedReader br; //バッファからデータを取り出すために使うクラス System.out.println("どのくらいの素数を入力したいですか？"); br=new BufferedReader(new InputStreamReader(System.in)); String str1 = br.readLine(); int sosu; sosu = Integer.parseInt(str1); int divisor; for(int i = 2; i <= sosu; i++) divisor = 0; for(int j = 1; j <= i; j++)

22 if(i % j == 0) { divisor++; } if(divisor == 2) int y; y = sosu % i; if(y!=0) System.out.print("素数="); System.out.println(i); System.out.println("上の中から2つの素数P,Qを入力してください。"); br=new BufferedReader(new InputStreamReader(System.in)); System.out.print("P="); String str2 = br.readLine(); System.out.print("Q=");

23 String str3 = br.readLine();
System.out.println("P="+ str2 + ",Q="+ str3); int p, q, n; p = Integer.parseInt(str2); q = Integer.parseInt(str3); n = p * q; System.out.println("N="+ n); int f, m, a, b; a = p-1; b = q-1; int d=1, l; if(p>q) { f = a % b; if(f==0) l = a; System.out.println("L="+ l); } else

24 do { d++; l = a * d; f = l % b; }while(f!=0); System.out.println("L="+ l); } else if(p<q) m = b % a; if(m==0) l = b; else

25 { d++; l = b * d; m = l % a; }while(m!=0); System.out.println("L="+ l); } else if(p==q) l = a; else System.out.println("エラーです。"); System.out.println("Lの値を入力してください。"); br=new BufferedReader(new InputStreamReader(System.in)); System.out.print("L="); String str4 = br.readLine(); int z;

26 z = Integer.parseInt(str4);
for(int i = 2; i <= z; i++) { divisor = 0; for(int j = 1; j <= i; j++) if(i % j == 0) divisor++; } if(divisor == 2) int y; y = z % i; if(y!=0) System.out.print("E="); System.out.println(i); }}

27 System.out.println("上のEの値から好きなEの値を1つ入力してください。");
br=new BufferedReader(new InputStreamReader(System.in)); System.out.print("E="); String str5 = br.readLine(); int x; x = Integer.parseInt(str5); int angou; System.out.print("ファイル名をタイピングしてください："); String filename=br.readLine(); br=new BufferedReader(new FileReader(filename)); String str; int k=0,h; int count=0,tmp; final int bit=0x0001; char[] cary; try{ PrintWriter pw = new PrintWriter(new BufferedWriter(new FileWriter("暗号化.txt"))); while((str=br.readLine())!=null) {

28 System.out.println(count+":"+str);
cary=str.toCharArray(); System.out.print(count+":"); for(int i=0;i<cary.length;i++) { int sum=0; for(int j=0;j<16;j++) int v=0; tmp = cary[i]&(bit<<(15-j)); tmp >>= 15-j; if(tmp==1) System.out.print("1"); k = 15-j; for(h=0;h<=k;h++) if(h==0) v = 1; }

29 else { v *= 2; } System.out.print("0"); k = 0; sum += v; System.out.println("["+cary[i]+"] "); System.out.println(Integer.toString(sum, 16)); angou = sum % n; //mod計算（冪乗法） for(int w = 1; w <= x-1; w++) angou *= sum;

30 angou = angou % n; if(w==x-1) { System.out.println("暗号化した 文字の数値は"+ angou +"です。"); System.out.println("暗号化した文字 　　　は"+(char)angou+"です。"); pw.println(angou); } System.out.println(); count++; br.close(); pw.close(); catch(IOException e){ System.out.println("入出力エラーです。"); ｝｝}

31 実行例

32 実行例

33 実行例

34 実行例

35 復号化プログラム

36 import java.io.*; class fukugouka { public static void main(String[] args) throws IOException BufferedReader br; System.out.println("NとEの値を入力してください。"); br=new BufferedReader(new InputStreamReader(System.in)); System.out.print("N="); String str1 = br.readLine(); int n; n = Integer.parseInt(str1); System.out.print("E="); String str2 = br.readLine(); int e; e = Integer.parseInt(str2);

37 int p=2; int c=1; while(c!=0) { c = n % p; if(c==0) int q; q = n / p; System.out.println("P="+p+",Q="+q); int a,b,f,m; a = p-1; b = q-1; int d=1, l; if(p>q) f = a % b; if(f==0)

38 l = a; System.out.println("L="+ l); } else { do d++; l = a * d; f = l % b; }while(f!=0); else if(p<q) m = b % a; if(m==0)

39 l = b; System.out.println("L="+ l); } else { do d++; l = b * d; m = l % a; }while(m!=0); else if(p==q) l = a; p++;｝

40 System.out.println("Lの値を入力してください。");
br=new BufferedReader(new InputStreamReader(System.in)); System.out.print("L="); String str3 = br.readLine(); int z; z = Integer.parseInt(str3); int d = 1; int l = 48; int s=0,m; while(s!=1) { m = e * d; s = m % z; if(s==1) System.out.println("Dの値は"+d); } d++;

41 System.out.println("Dの値を入力してください。");
br=new BufferedReader(new InputStreamReader(System.in)); System.out.print("D="); String str4 = br.readLine(); int y; y = Integer.parseInt(str4); int fukugou,g; try { FileReader in = new FileReader("暗号化.txt"); BufferedReader br1 = new BufferedReader(in); String line; while ((line = br1.readLine()) != null) System.out.println(line); g = Integer.parseInt(line); fukugou = g % n; for(int w = 1; w <= y-1; w++)

42 { fukugou *= g; fukugou = fukugou % n; if(w==y-1) System.out.println("復号化した文 字の数値は"+ fukugou +"です。"); System.out.println("復号化した文 字は"+(char)fukugou+"です。"); } br1.close(); in.close(); catch (IOException er) System.out.println(er); }｝｝

43 実行例

44 実行例

45 実行例