[SecureProgramming] RSA

RSA

[Step 01] Prime Number인 p, q를 선택하고 K를 계산
                    p, q    K = p X q
[Step 02] (p−1)과 (q−1)의 LCM인 φ 를 계산합니다.
                    φ=LCM((p−1)×(q−1))
[Step 03] φ와 서로소인 소수 e를 암호화키로 결정합니다.
                    e
[Step 04] 복호화 키인 d를 결정합니다.
                    d×e mod φ = 1
[Step 05] Message Encryption & Decryption
               Message Encryption =>  c = m^e mod K
               Message Decryption =>  m = c^d mod K

  ex) p = 11, q = 13 / K = p X q = 11 X 13 = 143
        φ = LCM((p−1)×(q−1)) = LCM(10×12) = 60
        e = 17
        d = 53 => 53 X 17 mod 60 = 1
        m = 6인 경우
        c = 6^17 mod 143 = 41
        m = 41^53 mod 143 = 6

 

 

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

public class RSA {
    private BigInteger p, q, K, φ;
    private BigInteger e, d;

    public RSA(BigInteger p, BigInteger q) {
        this.p = p;
        this.q = q;
        this.K = p.multiply(q);
        this.φ = LCM(p.subtract(BigInteger.ONE), q.subtract(BigInteger.ONE));
        this.e = BigInteger.valueOf(17);
        this.d = e.modInverse(φ);
    }

    public RSA() {
        this.p = generatePrimeNumber();
        this.q = generatePrimeNumber();
        this.K = p.multiply(q);
        this.φ = LCM(p.subtract(BigInteger.ONE), q.subtract(BigInteger.ONE));
        this.e = generateE();
        this.d = e.modInverse(φ);
    }

    public BigInteger LCM(BigInteger v1, BigInteger v2){
        BigInteger gcd = v1.gcd(v2);
        BigInteger lcm = v1.multiply(v2).divide(gcd);
        return lcm;
    }

    public BigInteger Encryption(BigInteger m){
        BigInteger c = m.pow(e.intValue()).mod(K);
        return c;
    }

    public BigInteger Decryption(BigInteger c){
        return c.pow(d.intValue()).mod(K);
    }

    public BigInteger generatePrimeNumber(){
        return BigInteger.probablePrime(1024, new Random());
    }

    public BigInteger generateE(){
        BigInteger newE = generatePrimeNumber();
        BigInteger gcdResult = newE.gcd(φ);
        while (gcdResult.equals(BigInteger.ONE)){
            newE = generatePrimeNumber();
            gcdResult = newE.gcd(φ);
        }
        return newE;
    }

    @Override
    public String toString() {
        return "RSA{" +
                "p=" + p +
                ", q=" + q +
                ", K=" + K +
                ", φ=" + φ +
                ", e=" + e +
                ", d=" + d +
                '}';
    }
}

 

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

public class RSATest {
    public static void main(String[] args) {
        RSA rsa = new RSA(BigInteger.valueOf(11), BigInteger.valueOf(13));
        System.out.println(rsa.toString());

        BigInteger encryptionData = rsa.Encryption(BigInteger.valueOf(6));
        BigInteger decryptionData = rsa.Decryption(encryptionData);

        System.out.println("암호화된 Data: " + encryptionData);
        System.out.println("복호화된 Data: " + decryptionData);

//        RSA rsa2 = new RSA();
//        System.out.println(rsa2.toString());

        System.out.println();
        modularTest01(3, 7);
        modularTest02();
        System.out.println();
        modularTest03();
        System.out.println();
        modularTest04();
    }

    public static void modularTest01(int A, int C) {
        for (int B = 0; B <= C - 1; B++) {
            System.out.println("B: " + B);
            System.out.println("A X B mod C: " + (A * B % C));
            int modResult = (A * B % C);
            System.out.printf("%d x %d mod %d = %d\n", A, B, C, modResult);
            if (modResult == 1) {
                System.err.println("B: " + B);
            }
        }
    }

    public static void modularTest02() {
        BigInteger A = BigInteger.probablePrime(1024, new Random());
        BigInteger C = BigInteger.probablePrime(1024, new Random());
        System.out.println();
        System.out.println("A: " + A);
        System.out.println("C: " + C);
        System.out.println("B: " + A.modInverse(C));
    }

    public static void modularTest03() {
        BigInteger A = BigInteger.valueOf(3);
        BigInteger C = BigInteger.valueOf(7);
        System.out.println("A: " + A);
        System.out.println("C: " + C);
        System.out.println("B: " + A.modInverse(C));
    }

    public static void modularTest04() {
        BigInteger A = BigInteger.valueOf(2);
        BigInteger C = BigInteger.valueOf(6);
        System.out.println("A: " + A);
        System.out.println("C: " + C);

        BigInteger gcd = A.gcd(C);
        if (gcd.equals(BigInteger.ONE)) {
            System.out.println("B: " + A.modInverse(C));
        } else {
            System.out.println("서로소가 아닙니다");
        }
    }
}

 

https://github.com/l2yujw/SecureProgramming/tree/main/rsa