JavaでRSAを実装してみる

　JavaでRSAを実装してみました。といっても基本的なところを実装しただけなので実用性はありません。
　Javaの場合は、JCE(Java Cryptography Extension)という標準APIがあるので、そちらを使う方が実用的です。おまけとして、JCEを使ったソースコードも載せておきます。

アルゴリズム

1. 大きい素数p, qを選びます。
2. n = pqとします。このときΦ(n) = (p-1)(q-1)になります。
3. k = Φ(n)とすると、オイラーの定理よりa^k = 1 (mod n) (式1)が成り立ちます。ただしaはnと互いに素な整数です。
4. a^ed = a(mod n) となるようなe, dを選びます。(式1)より、ed = 1 (mod k)を満たすようなeとdを選べばよいことが分かります。
5. 暗号化するときは、平文Tに対してC = T^e(mod n)とします。(e, n)が暗号化キーとなります。
6. 復号化するときは、暗号文Cに対してT = C^d(mod n)とします。(d, n)が複合化キーとなります。

シンプルなアルゴリズムですが、思いついた人はすごいですね。e乗したものをd乗すれば元に戻るし、逆にd乗したものをe乗すれば元に戻ります。これは、公開鍵で暗号化したものは秘密鍵で復号でき、秘密鍵で暗号化したものは公開鍵で復号できるということに対応しています。

ソースコード

BigInteger便利ですね。 冪乗高速化とか逆元の計算とか自分でやるつもりでしたが要りませんでした。

package com.kenjih.sample;

import java.math.BigInteger;
import java.util.Random;
import java.util.Scanner;

public class CustomRSASample {
    
    public static void main(String[] args) {
        System.out.println("Input text(ASCII only):");
        Scanner sc = new Scanner(System.in);
        String text = sc.nextLine();

        new CustomRSASample().run(text);
    }
    
    /**
     * RSA暗号化/復号化を行う(ASCII文字のみ対応).
     * 
     */
    public void run(String text) {
        
        // generate RSA keys 
        String[] keys = generateKeys(256);
        System.out.println("common key: " + keys[0]);
        System.out.println("public key: " + keys[1]);
        System.out.println("private key: " + keys[2]);
        
        // encrypt the text
        String encryptedText = encrypt(text, keys[1], keys[0]);
        System.out.println("cipher: " + encryptedText);
        
        // decrypt the text
        String decryptedText = decrypt(encryptedText, keys[2], keys[0]);
        System.out.println("plain: " + decryptedText);
    
    }
    
    /**
     * RSAのキーを生成する.
     * 
     * @return 16進数表記のキーを配列keys[]で返す.
     */
    public String[] generateKeys(int bitLength) {
        
        String[] keys = new String[3];
        Random rnd = new Random();
        
        for (;;) {
            BigInteger p = BigInteger.probablePrime(bitLength >> 1, rnd);
            BigInteger q = BigInteger.probablePrime(bitLength >> 1, rnd);
            
            if (p.equals(q))
                continue;
            
            // totient function of two different prime numbers
            BigInteger phi = p.subtract(BigInteger.ONE).multiply(q.subtract(BigInteger.ONE));
            
            BigInteger e = BigInteger.probablePrime(bitLength, rnd);
            if (e.gcd(phi).equals(BigInteger.ONE)) {
                keys[0] = p.multiply(q).toString(16);      // private/public key (common key)
                keys[1] = e.toString(16);                  // public key
                keys[2] = e.modInverse(phi).toString(16);  // private key
                break;
            }
        }
        
        return keys;
    }
    
    /**
     * 平文を暗号化する.
     * 
     */
    public String encrypt(String text, String publicKey, String commonKey) {
        BigInteger a = encode(text);
        BigInteger e = new BigInteger(publicKey, 16);
        BigInteger n = new BigInteger(commonKey, 16);
        
        return a.modPow(e, n).toString(16);
    }
    
    /**
     * 暗号文を復号化する.
     * 
     */
    public String decrypt(String hexCode, String privateKey, String commonKey) {
        BigInteger a = new BigInteger(hexCode, 16);
        BigInteger d = new BigInteger(privateKey, 16);
        BigInteger n = new BigInteger(commonKey, 16);
        
        return decode(a.modPow(d, n));
    }
    
    /**
     * ASCII文字を256進数のBigIntegerに変換する.
     * 
     */
    private BigInteger encode(String text) {
        BigInteger code = BigInteger.ZERO;
        
        for (int i = 0; i < text.length(); i++) {
            code = code.multiply(BigInteger.valueOf(256));
            code = code.add(BigInteger.valueOf(text.charAt(i)));
        }
            
        return code;
    }
    
    /**
     * 256進数のBigIntegerをASCII文字に変換する.
     * 
     */
    private String decode(BigInteger code) {
        StringBuilder sb = new StringBuilder();
        
        while (code.compareTo(BigInteger.ZERO) > 0) {
            int rem = code.mod(BigInteger.valueOf(256)).shortValue();
            sb.append((char)rem);
            code = code.divide(BigInteger.valueOf(256));
        }
        
        return sb.reverse().toString();
    }

}

実行結果は以下のようになります。

Input text(ASCII only):
hello, world.
common key: a8c7c7712a5ad3ef8244efe9f97e9edaf2586f74b4178075c88a82cf485197b7
public key: a1574aa5e7357321ffbdfffaa1f6135f3b5bbfde9389f9e21766860aaa643d49
private key: 84278732afc3e0d0de5c1acb800576c8ced6c983863c47aabd5671e656feebf9
cipher: 1159ca402742d7a8da249fdfc5265fd80d0146ccb1a3053e49c0961ae84f38f2
plain: hello, world.

JCEを使ったRSAの実装

上のソースコードはあくまでアルゴリズムを理解するためのもの（or プログラムの練習 or 学生の実験用）です。実用上はJCEを使うとよいです。
まず、RSAの実装を提供しているライブラリをインストールします。mavenを使っている場合は、以下をpom.xmlに追記します。

<dependency>
    <groupId>org.bouncycastle</groupId>
    <artifactId>bcprov-jdk16</artifactId>
    <version>1.45</version>
</dependency>

JCEのインターフェースを使って、上のライブラリの機能を使用します。

package com.kenjih.sample;

import java.security.Key;
import java.security.KeyPair;
import java.security.KeyPairGenerator;
import java.security.SecureRandom;
import java.security.Security;
import java.util.Scanner;

import javax.crypto.Cipher;

public class RSASample {
    public static void main(String[] args) {
        System.out.println("Input text:");
        Scanner sc = new Scanner(System.in);
        String text = sc.nextLine();

     new RSASample().run(text);
    }

    public void run(String text) {       
     Security.addProvider(new org.bouncycastle.jce.provider.BouncyCastleProvider());
        
     byte[] input = text.getBytes();
        
        try {
            Cipher cipher = Cipher.getInstance("RSA/None/NoPadding", "BC");
            SecureRandom random = new SecureRandom();
            
            // Generate RSA keys
            KeyPairGenerator generator = KeyPairGenerator.getInstance("RSA", "BC");
            generator.initialize(1024, random);
            KeyPair pair = generator.generateKeyPair();
            Key publicKey = pair.getPublic();
            Key privateKey = pair.getPrivate();
            System.out.println("public key: " + publicKey);
            System.out.println("private key: " + privateKey);
            
            // Encrypt a plain text
            cipher.init(Cipher.ENCRYPT_MODE, publicKey, random);
            byte[] cipherText = cipher.doFinal(input);
            System.out.println("cipher: " + new String(cipherText));
            
            // Decrypt a cipher text
            cipher.init(Cipher.DECRYPT_MODE, privateKey);
            byte[] plainText = cipher.doFinal(cipherText);
            System.out.println("plain : " + new String(plainText));

        } catch (Exception e) {
            e.printStackTrace();
        }
    }
}