공캐키 RSA 구조 알아보기 .der .pem

Asymmetric Encryption

 

공개키 (public-key cryptography)

사전에 비밀 키를 나눠가지지 않은 사용자들이 안전하게 통신할 수 있도록 한다. 공개 키 암호 방식에서는 공개 키와 비밀 키가 존재하며, 공개 키는 누구나 알 수 있지만 그에 대응하는 비밀 키는 키의 소유자만이 알 수 있다. 

공개키 암호학 방식에서 키 생성은 Trap door one way function에 기반을 둔다.

한 방향으로 계산이 쉬우나 다른 방향으로의 계산이 어렵다는 것을 이용한 방식이다.

키를 생성하는데 두 가지의 방법이 존재한다.

소인수분해

첫 번째로 소인수분해를 이용한 키 생성 방법이 있다.

p가 11이고 q가 13일때 N을 구하는 건 간단히 11x13 = 143 간단하게 구할 수 있지만 143을 소수인 p와 q를 구하려면 전자보다 어려워지는 것을 이용한 것이다.

이산대수

두 번째로 이산대수를 이용한 방법이 존재한다.

g, p, y가 주어져도 해당 x값을 구하는건 어려운 점을 이용한 방법이다.

공개키 암호방식

 

RSA 키 생성

RSA Key Generation

1. 서로 다른 큰 소수 p, q를 선택한다. 

2.  n = p * q

3. φ(n) => 오일러 Totient 함수, n보다 작은 자연수 중에서 n과 서로 소인 자연수의 개수를 구한다.

φ(n) = (p-1)(q-1)

4. φ(n)보다 작고 φ(n)과 서로소인 임의의 자연수 e를 선택한다.

gcd(e, φ(n)) = 1 (1 < e < φ(n) 만족하는 e를 선택)

5. 확장 유클리드 호제법을 이용해서 e mod φ(n) = 1인 d를 구한다.

공개 키(Public Key) : (N, e)
개인 키(Private Key) : d

기호	의미
p, q	매우 큰 서로 다른 소수
n	p*q의 합성수
gcd(a, b)	a와b의 최대 공약수
φ(n)	오일러 Totient함수로, φ(n)은 n보다 작은 자연수 중에서 n과 서로 소인 자연수의 개수
a mod n	모듈러 연산으로, a를 n로 나누었을 때 나머지 값
a≡ r mod n	a와 r은 n으로 나누었을 때 그 나머지가 같음 (a와 r은 합동)
e	n과 함께 공개되는 공개키로 암호화 지수에 사용
d	공개되지 않는 개인키로 복호화 지수에 사용
M	평문으로 공개키를 이용하여 암호화
C	암호문으로 개인키를 이용하여 복호화
KU	공개키로 KU= {e, n}으로 표기
KR	개인키로 KR= {d, n}으로 표기

 

 

RSA 공개 키, 개인 키 구하기

예를들어 p가 11이고 q가 3이라고 하자.
1. N = p * q를 구한다. => n = 33

2. φ(n)=(p-1)(q-1)를 계산한다. => (11-1)(3-1) = 20

3. φ(n)보다 작고 φ(n)과 서로소인 임의의 자연수 e를 선택한다. => e = 3 선택

이 때 20와 서로소 이면서 소수인 3을 선택한다. e = 3
ed = 1 mod (p-1)(q-1)에서 ed = 1 mod 20이 된다.

따라서 d = 7이다. (e가 3이므로)

공개 키 (N, e) : (33, 3)
개인 키 d : 7
 

 

Cipher Text 만들기

 

Plain Text 복호화 하기

 

RSA 암호화 기법에서의 지수 처리

 

  RSA 에서 모듈러 연산을 하기 위해서, 지수 연산을 많이 하게 됩니다. 암호화, 복호활할 때, 각각 쓰이게 되는데요, 이를 실수 연산을 한 뒤에 모듈러 연산을 하게 되면 메모리와 연산 속도에서 현저히 떨어지게 됩니다. 이를 조금더 쉽고 빠르게 연산하기 위해서 알고리즘이 존재합니다. 모듈러 하는 값의 바이너리 값을 이용해서 연산을 하는 방식입니다.

 

알고리즘을 연산 예제

ab mod n 의 연산을 하고자 할 때, 아래의 알고리즘을 이용하면 간단하게 연산을 수행할 수 있다.

여기서 b는 바이너리 형태로 존재한다. 즉, b는 bkbk-1…b0 로 표현된다.

 

위의 알고리즘을 이용하는 예제는 다음과 같다. ab mod n 연산에서 a=7, b = 560 =1000110000, n=561 라고 하면 아래와 같은 형태로 연산이 이루어진다.

 

 

RSA 키 파일 포맷

RSA Public Key를 표현하는 format 은 DER format 과 PEM format 이 있다. PKCS#1 표준에서는 RSA Key를 ASN.1 방식으로 표현하라고 규정하고 있다. (*ASN : Abstract Syntax Notation)

.DER (Distinguished Encoding Rule)
DER format은, ASN.1 구조에 맞추어 DER encoding한 것
2개 INTEGER 값의 SEQUENCE 로 표시

.PEM (Privacy-enhanced Electronic Mail)
Base64로 인코딩 된 ASCII text file 
 Header(--BEGIN PUBLIC KEY-- ) 와 Footer(---END PUBLIC KEY--)를 사용하고, ASCII Text형식으로 표현된다.
PEM은 DER format 이 binary 형식으로 되어 있기 때문에, Base64로 인코딩 함으로서 ASCII text 형식으로 변환한 것

.PEM = (Header) + base64_encode(.DER) + (Footer)

 

원래는 secure email에 사용되는 인코딩 포멧이었는데 더이상 email쪽에서는 잘 쓰이지 않고 인증서 또는 키값을 저장하는데 많이 사용된다.
-----BEGIN XXX-----, -----END XXX----- 로 묶여있는 text file을 보면 이 형식으로 인코딩 되어있다고 생각하면 된다. 
(담고있는 내용이 무엇인지에 따라 XXX 위치에 CERTIFICATE, RSA PRIVATE KEY 등의 키워드가 들어있다)

//PEM PrivateKey Example

-----BEGIN RSA PRIVATE KEY-----
MIICXAIBAAKBgQDBw2b5UiQQOeWrGr7AfK7sglIdmteUASLxKMnhBagtyZYgILBF
eI4Owf7C1FSibxAVMRbuAJ2QjkHu+gTp4aeNeaRMNQMowQTmK/sMgFK3jGwiAWEp
HdqVUJlKET6xvMFxhCvvEepyaan0UjU2TLVxrJq3IEFLoaNC7JdtyY+BMwIDAQAB
AoGAPq9Klwo95In2hT5ny7oKlTUr/6viZl1fwokhlozP9dAro0UwAamYu6mDE+DB
aLNpjpGNC35jeyqqpfd4s3lvTMKFShUJSul6u/oWxdWjA6fleLg/QNaV2/3LDEEo
KafEWI2cipEl9GiQHubFYMJU+jqRwMTRvfh/7sdXbFRU+UECQQD72vs89IPT0N1r
9hEMdkbim7W9DqTy8U2khil0Y/jFl9325Wa+fPKwl7zCyq5sIl4OR5vUGswnHcLi
MjL5hQHDAkEAxPOwni70rifF8ebMHcLHUmgRsEqVGQhmkABdAYydradjFgQlS8Qs
gBkbGjH0xF8/MCic66uYisAkTv/VXfib0QJAN0H9e4s+XTvnSOetJ+nPdaqqPje3
UyJEYcOZ1tKUY24FokUEvOiXKs2v+aEUkd8cec+WTfwvLKnn908CRiK7lwJAJlyE
0Tq6I9XRY12d8koHAtEMaPcN9XNCbtfzRaL672EEFry1+vz54fWB5udGEp2utBWl
Au5IZvYn3E9OYuBSkQJBANrzvuAV28H6i0ELisFx8nyCzTWJhT6AirSq2vILFOt9
PxdBVH/8NY9MlYJfiEEzEwebSh9kMaez9+rQy/agwxo=
-----END RSA PRIVATE KEY-----

 

OpenSSL RSA 키생성 커맨드

//private key
openssl genrsa -out private.pem 1024
//public key
openssl rsa -in private2.pem -pubout -out publickey.pem

 

Public-Private key syntax

Publickey와 Private 키 표준 구조체 정의 

// RSA Public Key syntax
RSAPublicKey ::= SEQUENCE {
    modulus           INTEGER,  -- n
    publicExponent    INTEGER   -- e
}

// RSA Private Key syntax
RSAPrivateKey ::= SEQUENCE {
    version           Version,
    modulus           INTEGER,  -- n
    publicExponent    INTEGER,  -- e
    privateExponent   INTEGER,  -- d
    prime1            INTEGER,  -- p
    prime2            INTEGER,  -- q
    exponent1         INTEGER,  -- d mod (p-1)
    exponent2         INTEGER,  -- d mod (q-1)
    coefficient       INTEGER,  -- (inverse of q) mod p
    otherPrimeInfos   OtherPrimeInfos OPTIONAL
}

 

PrivateKey를 PEM 포맷으로 출력한 결과와 Private 키에서 각 오프셋별 의미하는 값의미 (n, e, d, p, q)

> openssl asn1parse -in key.pm

 

Open SSH Key - > RSA PEM Key Example (by oddbit.com)

# python 2 based
import base64
import struct

# get the second field from the public key
keydata = "ssh-rsa AAAAB3NzaC1yc2EAAAADAQABAAABAQD7EZn/BzP26AWk/Ts2ymjpTXuXRiEWIWnHFTilOTcuJ/P1HfOwiy4RHC1rv59Yh/E6jbTx623+OGySJWh1IS3dAEaHhcGKnJaikrBn3ccdoNVkAAuL/YD7FMG1Z0SjtcZS6MoO8Lb9pkq6R+Ok6JQjwCEsB+OaVwP9RnVA+HSYeyCVE0KakLCbBJcD1U2aHP4+IH4OaXhZacpb9Ueja6NNfGrv558xTgfZ+fLdJ7cpg6wU8UZnVM1BJiUW5KFasc+2IuZR0+g/oJXaYwvW2T6XsMgipetCEtQoMAJ4zmugzHSQuFRYHw/7S6PUI2U03glFmULvEV+qIxsVFT1ng3pj lars@tiamat.house"
keydata = keydata.split()[1]
keydata = base64.b64decode(keydata)


parts = []
while keydata:
    # read the length of the data
    dlen = struct.unpack('>I', keydata[:4])[0]

    # read in <length> bytes
    data, keydata = keydata[4:dlen+4], keydata[4+dlen:]

    parts.append(data)

e_val = eval('0x' + ''.join(['%02X' % struct.unpack('B', x)[0] for x in parts[1]]))
n_val = eval('0x' + ''.join(['%02X' % struct.unpack('B', x)[0] for x in parts[2]]))

print(e_val)
print(n_val)

from pyasn1.type import univ

pkcs1_seq = univ.Sequence()
pkcs1_seq.setComponentByPosition(0, univ.Integer(n_val))
pkcs1_seq.setComponentByPosition(1, univ.Integer(e_val))

from pyasn1.codec.der import encoder as der_encoder

print '-----BEGIN RSA PUBLIC KEY-----'
print base64.encodestring(der_encoder.encode(pkcs1_seq))
print '-----END RSA PUBLIC KEY-----'

 

pycrypto (pycryptodome) RSA Example

from Crypto.PublicKey import RSA
from Crypto.Cipher import PKCS1_OAEP
import binascii

keyPair = RSA.generate(1024)

pubKey = keyPair.publickey()
print("Public key:  n=", hex(pubKey.n))
print("Public key:  e=", hex(pubKey.e))
pubKeyPEM = pubKey.exportKey()
print(pubKeyPEM.decode('ascii'))

print("Private key:  n=", hex(pubKey.n))
print("Private key:  d=", hex(keyPair.d))
privKeyPEM = keyPair.exportKey()
print(privKeyPEM.decode('ascii'))

msg = b'A message for encryption'
encryptor = PKCS1_OAEP.new(pubKey)
encrypted = encryptor.encrypt(msg)
print("Encrypted:", binascii.hexlify(encrypted))

decryptor = PKCS1_OAEP.new(keyPair)
decrypted = decryptor.decrypt(encrypted)
print('Decrypted:', decrypted)

 

gmpy2 (GMP & MPIR python)

import gmpy2
from gmpy2 import mpz

bit_count = 1024
rand_state = gmpy2.random_state(42)

def generate_prime(bits):
    temp = gmpy2.mpz_rrandomb(rand_state, bit_count)
    return gmpy2.next_prime(temp)

# Setting up the encryption
#
p = generate_prime(bit_count)
q = generate_prime(bit_count)
assert(p != q)

n = gmpy2.mul(p, q)
phi = gmpy2.mul(p-1, q-1)

print("p:", p)
print("q:", q)
print("n:", n)
print("phi:", phi)

# Key Generation
#
# Choose 1 < e < phi such that gcd(e, phi) = 1
# e will be our Public Key
#
# Choose d the multiplicative inverse of e in Z/phi
# d will be our Secret Key
e = gmpy2.mpz_random(rand_state, phi)
while (e <= 1 or gmpy2.gcd(e, phi) != 1):
    e = gmpy2.mpz_random(rand_state, phi)
assert(e > 1)
assert(gmpy2.gcd(e, phi) == 1)

d = gmpy2.invert(e, phi)
assert(d != 1)
assert(gmpy2.t_mod(e*d, phi) == 1)

print("PK(e):", e)
print("SK(d):", d)


# Encryption and Decryption
#
m = mpz(123456789101112131415)
c = gmpy2.powmod(m, e, n)
m_rec = gmpy2.powmod(c, d, n)

print("Original message:", m)
print("Ciphertext:", c)
print("Recovered message:", m_rec)

 

레퍼런스

Public-Key Cryptography Standards (PKCS) #1: RSA Cryptography Specifications Version 2.1
tools.ietf.org/html/rfc3447

samsclass blog -RSA Key Format 
samsclass.info/141/proj/pCH-RKF.htm 

ASN.1 JavaScript decoder
lapo.it/asn1js/

CONVERTING OPENSSH PUBLIC KEYS
blog.oddbit.com/post/2011-05-08-converting-openssh-public-keys/

cryptobook.nakov
cryptobook.nakov.com/asymmetric-key-ciphers/rsa-encrypt-decrypt-examples

Public Key Cryptography: RSA
mathybit.github.io/crypto-rsa