RSAアルゴリズムの紹介とJAVA実現


 
 


Posted by zeal on 2005-05-17 16:38 , 13469 characters |  + 0 - 1   English
: http://www.zeali.net/entry/58 MaDe1nZEAL
( JAVA/C++ ): rsa ,   ,   ,  download
RSA , , , 。

< >

RSA , :
p q
n=p*q
t=(p-1)*(q-1)
e, e<t e t ( 1)
d*e%t==1

: n  d  e

M (M <n)
c=(M**d)%n c
m=(c**e)%n m == M, c 。
:** , d e 。


n d , ;
n e ,e , 。
e , d , 。
d , e 。

rsa n,
n d e; n e
d。



< >

, :

p=47
q=59

n=p*q=2773
t=(p-1)*(q-1)=2668
e=63, e<t e t
perl e*d%t ==1 d:
C:\Temp>perl -e "foreach $i (1..9999){ print($i),last if $i*63%2668==1 }"
847
d=847


n=2773
d=847
e=63

M=244



c=M**d%n = 244**847%2773
perl :
C:\Temp>perl -Mbigint -e "print 244**847%2773"
465
d M c=465



e c , M:
m=c**e%n=465**63%2773 :
C:\Temp>perl -Mbigint -e "print 465**63%2773"
244
e c m=244 , M 。


< >


ascii M , 16
, 3 , 01F

#!/usr/bin/perl -w
#RSA
#watercloud 2003-8-12
#

use strict;
use Math::BigInt;

my %RSA_CORE = (n=>2773,e=>63,d=>847); #p=47,q=59

my $N=new Math::BigInt($RSA_CORE{n});
my $E=new Math::BigInt($RSA_CORE{e});
my $D=new Math::BigInt($RSA_CORE{d});

print "N=$N D=$D E=$E
";

sub RSA_ENCRYPT
{

    my $r_mess = shift @_;
    my ($c,$i,$M,$C,$cmess);

    for($i=0;$i < length($$r_mess);$i++)
    {

        $c=ord(substr($$r_mess,$i,1));
        $M=Math::BigInt->new($c);
        $C=$M->copy(); $C->bmodpow($D,$N);
        $c=sprintf "%03X",$C;
        $cmess.=$c;
    }

    return \$cmess;
}


sub RSA_DECRYPT
{

    my $r_mess = shift @_;
    my ($c,$i,$M,$C,$dmess);

    for($i=0;$i < length($$r_mess);$i+=3)
    {

        $c=substr($$r_mess,$i,3);
        $c=hex($c);
        $M=Math::BigInt->new($c);
        $C=$M->copy(); $C->bmodpow($E,$N);
        $c=chr($C);
        $dmess.=$c;
    }

    return \$dmess;
}


my $mess="RSA ~~~";
$mess=$ARGV[0] if @ARGV >= 1;
print "",$mess,"
";

my $r_cmess = RSA_ENCRYPT(\$mess);
print "",$$r_cmess,"
";

my $r_dmess = RSA_DECRYPT($r_cmess);
print "",$$r_dmess,"
";

#EOF



C:\Temp>perl rsa-test.pl
N=2773  D=847  E=63
:RSA ~~~
:5CB6CD6BC58A7709470AA74A0AA74A0AA74A6C70A46C70A46C70A4
:RSA ~~~


C:\Temp>perl rsa-test.pl (xfocus)
N=2773  D=847  E=63
: (xfocus)
:3393EC12F0A466E0AA9510D025D7BA0712DC3379F47D51C325D67B
: (xfocus)



< >

,rsa n , n , ,
RSAKit、RSATool N D E。
, 1024 N D E :

n=0x328C74784DF31119C526D18098EBEBB943B0032B599CEE13CC2BCE7B5FCD15F90B66EC3A85F5005D
BDCDED9BDFCB3C4C265AF164AD55884D8278F791C7A6BFDAD55EDBC4F017F9CCF1538D4C2013433B383B
47D80EC74B51276CA05B5D6346B9EE5AD2D7BE7ABFB36E37108DD60438941D2ED173CCA50E114705D7E2
BC511951

d=0x10001

e=0xE760A3804ACDE1E8E3D7DC0197F9CEF6282EF552E8CEBBB7434B01CB19A9D87A3106DD28C523C2995
4C5D86B36E943080E4919CA8CE08718C3B0930867A98F635EB9EA9200B25906D91B80A47B77324E66AFF2
C4D70D8B1C69C50A9D8B4B7A3C9EE05FFF3A16AFC023731D80634763DA1DCABE9861A4789BD782A592D2B
1965



M=0x11111111111122222222222233333333333

, perl :

A) d M :
c=M**d%n :
C:\Temp>perl -Mbigint -e " $x=Math::BigInt->bmodpow(0x11111111111122222222222233
333333333, 0x10001, 0x328C74784DF31119C526D18098EBEBB943B0032B599CEE13CC2BCE7B5F
CD15F90B66EC3A85F5005DBDCDED9BDFCB3C4C265AF164AD55884D8278F791C7A6BFDAD55EDBC4F0
17F9CCF1538D4C2013433B383B47D80EC74B51276CA05B5D6346B9EE5AD2D7BE7ABFB36E37108DD6
0438941D2ED173CCA50E114705D7E2BC511951);print $x->as_hex"
0x17b287be418c69ecd7c39227ab681ac422fcc84bb35d8a632543b304de288a8d4434b73d2576bd
45692b007f3a2f7c5f5aa1d99ef3866af26a8e876712ed1d4cc4b293e26bc0a1dc67e247715caa6b
3028f9461a3b1533ec0cb476441465f10d8ad47452a12db0601c5e8beda686dd96d2acd59ea89b91
f1834580c3f6d90898

d M :
c=0x17b287be418c69ecd7c39227ab681ac422fcc84bb35d8a632543b304de288a8d4434b73d2576bd
45692b007f3a2f7c5f5aa1d99ef3866af26a8e876712ed1d4cc4b293e26bc0a1dc67e247715caa6b
3028f9461a3b1533ec0cb476441465f10d8ad47452a12db0601c5e8beda686dd96d2acd59ea89b91
f1834580c3f6d90898



B) e c :

m=c**e%n :
C:\Temp>perl -Mbigint -e " $x=Math::BigInt->bmodpow(0x17b287be418c69ecd7c39227ab
681ac422fcc84bb35d8a632543b304de288a8d4434b73d2576bd45692b007f3a2f7c5f5aa1d99ef3
866af26a8e876712ed1d4cc4b293e26bc0a1dc67e247715caa6b3028f9461a3b1533ec0cb4764414
65f10d8ad47452a12db0601c5e8beda686dd96d2acd59ea89b91f1834580c3f6d90898,  0xE760A
3804ACDE1E8E3D7DC0197F9CEF6282EF552E8CEBBB7434B01CB19A9D87A3106DD28C523C29954C5D
86B36E943080E4919CA8CE08718C3B0930867A98F635EB9EA9200B25906D91B80A47B77324E66AFF
2C4D70D8B1C69C50A9D8B4B7A3C9EE05FFF3A16AFC023731D80634763DA1DCABE9861A4789BD782A
592D2B1965,  0x328C74784DF31119C526D18098EBEBB943B0032B599CEE13CC2BCE7B5FCD15F90
B66EC3A85F5005DBDCDED9BDFCB3C4C265AF164AD55884D8278F791C7A6BFDAD55EDBC4F017F9CCF
1538D4C2013433B383B47D80EC74B51276CA05B5D6346B9EE5AD2D7BE7ABFB36E37108DD60438941
D2ED173CCA50E114705D7E2BC511951);print $x->as_hex"
0x11111111111122222222222233333333333
( P4 1.6G 5 )

e m=0x11111111111122222222222233333333333  == M


C) RSA
RSA , , RSA ,
, ,
RSA 。


, 1024 N
1024 RSA, 2048 。

----------------------------------------------------------

RSA JAVA :

filename:RSA.java

view plain print ?
  1. /* 
  2.  
  3. * Created on Mar 3, 2005 
  4.  
  5. * 
  6.  
  7. * TODO To change the template for this generated file go to 
  8.  
  9. * Window - Preferences - Java - Code Style - Code Templates 
  10.  
  11. */  
  12.   
  13.   
  14. import java.math.BigInteger;  
  15.   
  16. import java.io.InputStream;  
  17.   
  18. import java.io.OutputStream;  
  19.   
  20. import java.io.FileInputStream;  
  21.   
  22. import java.io.FileOutputStream;  
  23.   
  24. import java.io.FileNotFoundException;  
  25.   
  26. import java.io.IOException;  
  27.   
  28. import java.io.FileWriter;  
  29.   
  30. import java.io.FileReader;  
  31.   
  32. import java.io.BufferedReader;  
  33.   
  34. import java.util.StringTokenizer;  
  35.   
  36.   
  37. /** 
  38.  
  39. * @author Steve 
  40.  
  41. * 
  42.  
  43. * TODO To change the template for this generated type comment go to 
  44.  
  45. * Window - Preferences - Java - Code Style - Code Templates 
  46.  
  47. */  
  48.   
  49. public class RSA {  
  50.   
  51.      
  52.   
  53.     /** 
  54.  
  55.      * BigInteger.ZERO 
  56.  
  57.      */  
  58.   
  59.     private static final BigInteger ZERO = BigInteger.ZERO;  
  60.   
  61.      
  62.   
  63.     /** 
  64.  
  65.      * BigInteger.ONE 
  66.  
  67.      */  
  68.   
  69.     private static final BigInteger ONE = BigInteger.ONE;  
  70.   
  71.      
  72.   
  73.     /** 
  74.  
  75.      * Pseudo BigInteger.TWO 
  76.  
  77.      */  
  78.   
  79.     private static final BigInteger TWO = new BigInteger("2");  
  80.   
  81.      
  82.   
  83.     private BigInteger myKey;  
  84.   
  85.      
  86.   
  87.     private BigInteger myMod;  
  88.   
  89.      
  90.   
  91.     private int blockSize;  
  92.   
  93.      
  94.   
  95.     public RSA (BigInteger key, BigInteger n, int b) {  
  96.   
  97.         myKey = key;  
  98.   
  99.         myMod = n;  
  100.   
  101.         blockSize = b;  
  102.   
  103.     }  
  104.   
  105.      
  106.   
  107.     public void encodeFile (String filename) {  
  108.   
  109.         byte[] bytes = new byte[blockSize / 8 + 1];  
  110.   
  111.         byte[] temp;  
  112.   
  113.         int tempLen;  
  114.   
  115.         InputStream is = null;  
  116.   
  117.         FileWriter writer = null;  
  118.   
  119.         try {  
  120.   
  121.              is = new FileInputStream(filename);  
  122.   
  123.              writer = new FileWriter(filename + ".enc");  
  124.   
  125.         }  
  126.   
  127.         catch (FileNotFoundException e1){  
  128.   
  129.             System.out.println("File not found: " + filename);  
  130.   
  131.         }  
  132.   
  133.         catch (IOException e1){  
  134.   
  135.             System.out.println("File not found: " + filename + ".enc");  
  136.   
  137.         }  
  138.   
  139.          
  140.   
  141.         /** 
  142.  
  143.          * Write encoded message to 'filename'.enc 
  144.  
  145.          */  
  146.   
  147.         try {  
  148.   
  149.             while ((tempLen = is.read(bytes, 1, blockSize / 8)) > 0) {  
  150.   
  151.                 for (int i = tempLen + 1; i < bytes.length; ++i) {  
  152.   
  153.                     bytes[i] = 0;  
  154.   
  155.                 }   
  156.   
  157.                 writer.write(encodeDecode(new BigInteger(bytes)) + " ");  
  158.   
  159.             }  
  160.   
  161.         }  
  162.   
  163.         catch (IOException e1) {  
  164.   
  165.             System.out.println("error writing to file");  
  166.   
  167.         }  
  168.   
  169.          
  170.   
  171.         /** 
  172.  
  173.          * Close input stream and file writer 
  174.  
  175.          */  
  176.   
  177.         try {  
  178.   
  179.             is.close();  
  180.   
  181.             writer.close();  
  182.   
  183.         }  
  184.   
  185.         catch (IOException e1) {  
  186.   
  187.             System.out.println("Error closing file.");  
  188.   
  189.         }  
  190.   
  191.     }  
  192.   
  193.      
  194.   
  195.     public void decodeFile (String filename) {  
  196.   
  197.          
  198.   
  199.         FileReader reader = null;  
  200.   
  201.         OutputStream os = null;  
  202.   
  203.         try {  
  204.   
  205.             reader = new FileReader(filename);  
  206.   
  207.             os = new FileOutputStream(filename.replaceAll(".enc"".dec"));  
  208.   
  209.         }  
  210.   
  211.         catch (FileNotFoundException e1) {  
  212.   
  213.             if (reader == null)  
  214.   
  215.                 System.out.println("File not found: " + filename);  
  216.   
  217.             else  
  218.   
  219.                 System.out.println("File not found: " + filename.replaceAll(".enc""dec"));  
  220.   
  221.         }  
  222.   
  223.          
  224.   
  225.         BufferedReader br = new BufferedReader(reader);  
  226.   
  227.         int offset;  
  228.   
  229.         byte[] temp, toFile;  
  230.   
  231.         StringTokenizer st = null;  
  232.   
  233.         try {  
  234.   
  235.             while (br.ready()) {  
  236.   
  237.                 st = new StringTokenizer(br.readLine());  
  238.   
  239.                 while (st.hasMoreTokens()){  
  240.   
  241.                     toFile = encodeDecode(new BigInteger(st.nextToken())).toByteArray();  
  242.   
  243.                     System.out.println(toFile.length + " x " + (blockSize / 8));  
  244.   
  245.                      
  246.   
  247.                     if (toFile[0] == 0 && toFile.length != (blockSize / 8)) {  
  248.   
  249.                         temp = new byte[blockSize / 8];  
  250.   
  251.                         offset = temp.length - toFile.length;   
  252.   
  253.                         for (int i = toFile.length - 1; (i <= 0) && ((i + offset) <= 0); --i) {  
  254.   
  255.                             temp[i + offset] = toFile[i];  
  256.   
  257.                         }  
  258.   
  259.                         toFile = temp;  
  260.   
  261.                     }  
  262.   
  263.                      
  264.   
  265.                     /*if (toFile.length != ((blockSize / 8) + 1)){ 
  266.  
  267.                         temp = new byte[(blockSize / 8) + 1]; 
  268.  
  269.                         System.out.println(toFile.length + " x " + temp.length); 
  270.  
  271.                         for (int i = 1; i < temp.length; i++) { 
  272.  
  273.                             temp[i] = toFile[i - 1]; 
  274.  
  275.                         } 
  276.  
  277.                         toFile = temp; 
  278.  
  279.                     } 
  280.  
  281.                     else 
  282.  
  283.                         System.out.println(toFile.length + " " + ((blockSize / 8) + 1));*/  
  284.   
  285.                     os.write(toFile);  
  286.   
  287.                 }  
  288.   
  289.             }  
  290.   
  291.         }  
  292.   
  293.         catch (IOException e1) {  
  294.   
  295.             System.out.println("Something went wrong");  
  296.   
  297.         }  
  298.   
  299.          
  300.   
  301.         /** 
  302.  
  303.          * close data streams 
  304.  
  305.          */  
  306.   
  307.         try {  
  308.   
  309.             os.close();  
  310.   
  311.             reader.close();  
  312.   
  313.         }  
  314.   
  315.         catch (IOException e1) {  
  316.   
  317.             System.out.println("Error closing file.");  
  318.   
  319.         }  
  320.   
  321.     }  
  322.   
  323.      
  324.   
  325.     /** 
  326.  
  327.      * Performs <tt>base</tt>^<sup><tt>pow</tt></sup> within the modular 
  328.  
  329.      * domain of <tt>mod</tt>. 
  330.  
  331.      * 
  332.  
  333.      * @param base the base to be raised 
  334.  
  335.      * @param pow the power to which the base will be raisded 
  336.  
  337.      * @param mod the modular domain over which to perform this operation 
  338.  
  339.      * @return <tt>base</tt>^<sup><tt>pow</tt></sup> within the modular 
  340.  
  341.      * domain of <tt>mod</tt>. 
  342.  
  343.      */  
  344.   
  345.     public BigInteger encodeDecode(BigInteger base) {  
  346.   
  347.         BigInteger a = ONE;  
  348.   
  349.         BigInteger s = base;  
  350.   
  351.         BigInteger n = myKey;  
  352.   
  353.          
  354.   
  355.         while (!n.equals(ZERO)) {  
  356.   
  357.             if(!n.mod(TWO).equals(ZERO))  
  358.   
  359.                 a = a.multiply(s).mod(myMod);  
  360.   
  361.              
  362.   
  363.             s = s.pow(2).mod(myMod);  
  364.   
  365.             n = n.divide(TWO);  
  366.   
  367.         }  
  368.   
  369.          
  370.   
  371.         return a;  
  372.   
  373.     }     
  374.   
  375. }  

RSA JAVA :

1. http://www.javafr.com/code.aspx?ID=27020  RSA :
           JavaFR_RSA_Source.rar 

2. http://www.ferrara.linux.it/Members/lucabariani/RSA/implementazioneRsa/  :
           sorgentiJava.tar.gz  -
           algoritmoRSA.jar - jar

RSA php : php RSA

VB RSA ( psc1 RSA ):
           vb_PSC1_RSA.rar

RSA JavaScript : http://www.ohdave.com/rsa/