icon

sambaiz-net
github
google maps
board game arena
aws golang machinelearning python etl kubernetes web fluentd gcp ios ...

RSA暗号とPEM/DERの構造

crypto

RSA暗号とは

c ≡ m^e (mod n) で暗号化し、m ≡ c^d (mod n) で複合する暗号。 e と n が公開鍵で d が秘密鍵。n はとても大きく近くない素数 p,q の積で、 これを公開しても p * q に素因数分解できないのがこの暗号の前提になっている。 768bit(10進数で232桁)では既に解読されているので、少なくとも1024bit以上にする。

eはEuler totient function(1~nまでの整数でnと互いに素なものの個数 φ(n)=(p-1)(q-1))未満で互いに素な正の整数で、小さすぎても大きすぎても良くない。2^16 + 1 = 65537 がよく使われる。

d は ed ≡ 1 (mod φ(n)) を満たす値にする。

例

例として (p,q) = (193,709) とすると各変数は次のようになる。

  • n = p * q = 136837
  • φ(n) = (p-1)(q-1) = 135936
  • e = 65537 < φ(n)

秘密鍵 d は 65537d ≡ 1 (mod 135936) の式を変形した 65537d - 135936*x = gcd(65537,135936) = 1 を、次のように 135936 と 65537を残しながら展開していく、拡張されたユークリッドの互除法で求める。

拡張されたユークリッドの互除法

これをコードに表したのがこれ。

const d = (phi,e) => {
    let history = {[phi]: [1,0], [e]:[0,1]} // [x,y] => φ * x + e * y
    let x = phi
    let y = e
    while(y > 1){
        const nextY = x % y
        history[x % y] = history[x].map((vx,index) => vx - history[y][index] * Math.floor(x/y))
        x = y
        y = nextY;
    }
    return history;
}

const phi = (193-1) * (709-1)
const e = 65537
const result = d(phi,e);
console.log(result);
console.log(`1 = ${phi}*${result[1][0]} + ${e}*${result[1][1]}`);

{ '1': [ 9503, -19711 ],
  '6': [ -8519, 17670 ],
  '7': [ 984, -2041 ],
  '62': [ -647, 1342 ],
  '69': [ 337, -699 ],
  '131': [ -310, 643 ],
  '200': [ 27, -56 ],
  '2331': [ -13, 27 ],
  '4862': [ 1, -2 ],
  '65537': [ 0, 1 ],
  '135936': [ 1, 0 ] }
1 = 135936*9503 + 65537*-19711

1 = 135936*-65537 + 65537135936 = 135936(9503-65537) + 65537*(-19711 + 135936) なので d=116225 となる。

平文が 12345 のとき、公開鍵 e,n で暗号化すると (12345 ** 65537) % 136837 = 6964 になり、 これを秘密鍵 d で復号することで (6964 ** 116225) % 136837 = 12345 のように元の平文が得られる。

鍵ファイルの生成

ssh-keygenで生成されるようなPEMファイルを作る。

用語

DER(Distinguished Encoding Rules)は ASN.1(Abstract Syntax Notation One)記法で定義されたデータを エンコードするルールの一つ。1a(INTEGER) 0b(byte) 68 65 6c 6c 6f 20 77 6f 72 6c 64(“hello world”)) のようなtype-length-valueで表す。

PEM(Privacy-enhanced Electronic Mail)は 公開鍵のフォーマットの定義X.509で 定められている拡張子で、Base64でエンコードされたDER。

PKCS(Public-Key Cryptography Standards)は公開鍵暗号における標準仕様を定めたもの。PKCS#1(RFC2313)にはRSA暗号の方式やASN.1表現などが含まれている。

RFC2313に書かれているASN.1を見ながらPEMの内容を確認する。

RSAPrivateKey

n,e,dに加えて生成に使った素数まで含んでいる。

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 }

   Version ::= INTEGER

pemを生成し、Base64デコードしてDERにする。

$ openssl genrsa 1024 > secret.pem
$ cat secret.pem 
-----BEGIN RSA PRIVATE KEY-----
(内容)
-----END RSA PRIVATE KEY-----

$ echo (内容) | base64 -D | xxd
00000000: 3082 025c 0201 0002 8181 .... .... .... 
00000080: .... .... .... .... .... ..02 0301 0001
00000090: 0281 80..
00000110: .... ..02 41.. 
00000150: .... .... .... 0241 ....
00000190: .... .... .... .... ..02 40.. 
000001d0: .... .... .... .... .... ..02 41.. ....  
00000210: .... .... .... .... .... .... .... 0240

整理するとこんな感じ。

[0000] 30 82 02 5c       
(30->Type=SEQUENCE 82->先頭bitが1なのでlengthに使うバイト数(2bytes) 025c->Length=605bytes)

  [0000] 02 01 00
  (version: 02->Type=INTEGER, 01->先頭が0なのでそのままLength=3bytes, Value=0)

  [0000] 02 81 81 .. 
  (modulus: Type=INTEGER, Length=129bytes)

  [0080] 02 03 01 00 01 
  (publicExponent: Type=INTEGER, Length=3bytes, Value=65537)

  [0090] 02 81 80 ..
  (privateExponent: Type=INTEGER, Length=128bytes)

  [0110] 02 41 ..
  (prime1: Type=INTEGER, Length=65bytes)

  [0150] 02 41 .. 
  (prime2: Type=INTEGER, Length=65bytes)

  [0190] 02 40 ..
  (exponent1: Type=INTEGER, Length=64bytes)

  [01d0] 02 41 ..
  (exponent2: Type=INTEGER, Length=65bytes)

  [0210] 02 40 ..
  (coefficient: Type=INTEGER, Length=64bytes)

RSAPublicKey

nとeだけ。

RSAPublicKey ::= SEQUENCE {
     modulus INTEGER, -- n
     publicExponent INTEGER -- e }

秘密鍵から公開鍵を生成して同様にDERにする。

$ openssl rsa -pubout < secret.pem > public.pem
$ cat public.pem 
-----BEGIN PUBLIC KEY-----
(内容)
-----END PUBLIC KEY-----

$ echo (内容) | base64 -D | xxd
00000000: 3081 9f30 0d06 092a 8648 86f7 0d01 0101
00000010: 0500 0381 8d00 3081 8902 8181 .... ....
00000090: .... .... .... .... .... .... ..02 0301 
000000a0: 0001

[0000] 30 81 9f
(Type=SEQUENCE, Length=159bytes)
  [0000] 30 0d
  (Type=SEQUENCE, Length=13bytes)
    [0000] 06 09 2a 86 48 86 f7 0d 01 01 01
    (Type=OBJECT IDENTIFIER, Length=9bytes, 
    value=http://www.oid-info.com/get/1.2.840.113549.1.1.1
          最上位ビットは区切りのサイン
          2a ((0)010 1010) => 40 * 1 + 2 => 1(iso) 2(member-body)
          86 48 ((1)000 0110 (0)100 1000) => 840(us)
          86 f7 0d ((1)000 0110 (1)111 0111 (0)000 1101) => 113549(rsadsi)
          01 ((0)000 0001) => 1(pkcs)
          01 ((0)000 0001) => 1(pcks-1)
          01 ((0)000 0001) => 1(rsaEncryption)

    [0010] 05 00
    (アルゴリズムパラメータ: Type=Null 0byte)

    [0010] 03 81 8d 00 
    (Type=BIT STRING, 141bytes, 最終byteの切り捨て0bit)

      [0010] 30 81 89
      (Type=SEQUENCE, 137bytes)

        [0010] 02 81 81 ..
        (modulus: Type=INTEGER, Length=129bytes)

        [0090] 02 03 01 00 01
        (publicExponent: Type=INTEGER, Length=3bytes, Value=65537)

digestInfo

署名に使う。

digestInfo ::= SEQUENCE {
     digestAlgorithm DigestAlgorithmIdentifier,
     digest Digest 
}

Digest ::= OCTET STRING

digestAlgorithmでデータをハッシュ化したものをdigestInfoに詰め、秘密鍵で暗号化したものを署名とし、 公開鍵で複合してdigestと実際のハッシュ値が一致することを確認する。 RSASSA-PKCS1-v1_5では暗号化の前に 00 01 ff ff ff .. 00 のパディングを加える。

参考

A Method for Obtaining Digital Signatures and Public-Key Cryptosystems

自堕落な技術者の日記 : 図説RSA署名の巻

RSA 秘密鍵/公開鍵ファイルのフォーマット - bearmini’s blog

openssl - How is OID 2a 86 48 86 f7 0d parsed as 1.2.840.113549? - Cryptography Stack Exchange