RSAの暗号化、復号を計算してみる。


といいつつ、署名と検証です。
愛のメッセージに署名を付与して改ざんを防ぎます。

~~.Net の RSACryptServiceProvider が 512bit 以上の鍵しか利用できないので、自前で計算する羽目になった~~

## opensslにて手順の確認

以下のようにして生成した `message.bin`, `sign.bin`, `public-key.pem` を渡すことで、私がしたためたメッセージだということを保証します。

```
$ openssl genrsa 32 > private-key.pem
Generating RSA private key, 32 bit long modulus
.+++++++++++++++++++++++++++
.+++++++++++++++++++++++++++
e is 65537 (0x10001)
-----BEGIN RSA PRIVATE KEY-----
MC0CAQACBQC/R561AgMBAAECBQCH+mbVAgMA+G8CAwDFGwICKYMCAmr9AgMA3A4=
-----END RSA PRIVATE KEY-----

$ openssl rsa -in private-key.pem -pubout -out public-key.pem
writing RSA key
-----BEGIN PUBLIC KEY-----
MCAwDQYJKoZIhvcNAQEBBQADDwAwDAIFAL9HnrUCAwEAAQ==
-----END PUBLIC KEY-----

$ echo -en "\x6C\x6F\x76\x65" > message.bin

$ hexdump message.bin
0000000 6f6c 6576
0000004

$ openssl rsautl -raw -sign -inkey private-key.pem -in message.bin > sign.bin

$ hexdump sign.bin
0000000 d152 de16
0000004

$ openssl rsautl -raw -verify -pubin -inkey public-key.pem -in sign.sig > sign.verified.bin

$ hexdump sign.verified.bin
0000000 6f6c 6576
0000004
```

## PEMをデコードする

Roslyn の C# Interactive (VS2017) で確認しながら実行していったのでメモとして掲載。

1. `s/-.*-//g` でヘッダとフッダを削除し、Base64部分のみを取り出す。

    ```c#
    var privKey = "-----BEGIN RSA PRIVATE KEY-----\nMC0CAQACBQC/R561AgMBAAECBQCH+mbVAgMA+G8CAwDFGwICKYMCAmr9AgMA3A4=\n-----END RSA PRIVATE KEY-----";
    var regexHeader = new System.Text.RegularExpressions.Regex(@"-.*-");
    var regexReturn = new System.Text.RegularExpressions.Regex(@"\n");
    var privKeyBase64 = regexReturn.Replace(regexHeader.Replace(privKey, ""), "");
    WriteLine(priveKeyBase64);
    // MC0CAQACBQC/R561AgMBAAECBQCH+mbVAgMA+G8CAwDFGwICKYMCAmr9AgMA3A4=
    ```

1. base64をdecodeする。

    ```c#
    var privKeyBuf = Convert.FromBase64String(privKeyBase64);
    WriteLine(BitConverter.ToString(privKeyBuf));
    // 30-2D-02-01-00-02-05-00-BF-47-9E-B5-02-03-01-00-01-02-05-00-87-FA-66-D5-02-03-00-F8-6F-02-03-00-C5-1B-02-02-29-83-02-02-6A-FD-02-03-00-DC-0E
    ```

1. RSAのDERは1Byte目が `0x30` と決まっているのでそれ以外であれば弾く。

    ```c#
    var index = 0;
    if (privKeyBuf[index++] != 0x30) { throw new ArgumentException("The Format Private Key is not PEM."); }
    ```

1. DER内の最初のコンテンツの長さを読み、コンテンツを取得する。(それ以外は捨てる)

    ```c#
    int contentLength = 0;
    //次のByteの最上位Bitが立っていれば、その下位7bitでコンテンツの長さの長さ(タイポじゃないよ)を表す。
    if ((privKeyBuf[index] & 0x80) != 0 )
    { 
      // コンテンツの長さを取得する。
      byte[] emptyBytes = {0, 0, 0, 0};
      byte[] lengthBytes = new byte[privKeyBuf[index] & 0x7F];
      Array.Copy(privKeyBuf, ++index, lengthBytes, 0, privKeyBuf[index] & 0x7F);
      index += privKeyBuf[index] & 0x7F;
      if (lengtsBytes >= 4)
      {
        // Intにしてるので4byte以上の場合はパースできない。
        throw new ArgumentException("PEM file is too large.");
      }
      lengthBytes = emptyBytes.Concat(lengthBytes).ToArray();
      // エンディアンによって処理が違う
      if (BitConverter.IsLittleEndian)
      {
        contentLength = (int)BitConverter.ToUInt32(emptyBytes, emptyBytes.Length - 4);
      }
      else
      {
        contentLength = (int)BitConverter.ToUInt32(emptyBytes.Reverse().ToArray(), 0);
      }
      if (contentLength == 0) {
        // Intにキャスト失敗した場合はパースできない。
        throw new ArgumentException("PEM file is too large.");
      }
    }
    else
    {
      // 最上位Bitが立っていなければ、そのbyte自体がコンテンツの長さを表す。
      contentLength = privKeyBuf[index++];
    }
    byte[] privKeyContents = new byte[contentLength];
    Array.Copy(privKeyBuf, index, privKeyContents, 0, contentLength);
    // byte[45] { 2, 1, 0, 2, 5, 0, 191, 71, 158, 181, 2, 3, 1, 0, 1, 2, 5, 0, 135, 250, 102, 213, 2, 3, 0, 248, 111, 2, 3, 0, 197, 27, 2, 2, 41, 131, 2, 2, 106, 253, 2, 3, 0, 220, 14 }
    ```

1. コンテンツをパースする

    構造は次のように定義されている。

    ```
    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
    }
    ```

    この辺は手計算。

    1. ID: 2(Int), Length: 1, Contents: byte[1] { 0 }                     = version: 0
        * したがって、 `otherPrimeInfos` は存在しない。
    1. ID: 2(Int), Length: 5, Contents: byte[5] { 0, 191, 71, 158, 181 }  = modulus: 3,209,141,941
    1. ID: 2(Int), Length: 3, Contents: byte[3] { 1, 0, 1 }               = publicExponent: 65,537
    1. ID: 2(Int), Length: 5, Contents: byte[5] { 0, 135, 250, 102, 213 } = privateExponent: 2,281,334,485
    1. ID: 2(Int), Length: 3, Contents: byte[3] { 0, 248, 111 }           = prime1: 63,599
    1. ID: 2(Int), Length: 3, Contents: byte[3] { 0, 197, 27 }            = prime2: 50,459
    1. ID: 2(Int), Length: 2, Contents: byte[2] { 41, 131 }               = exponent1: 10,627
    1. ID: 2(Int), Length: 2, Contents: byte[2] { 106, 253 }              = exponent2: 27,389
    1. ID: 2(Int), Length: 3, Contents: byte[3] { 0, 220, 14 }            = coefficient: 56,334

## 署名する

今回の鍵は32bitなので平文は4文字まで。平文は "love" とします。
これをbyte列にすると `byte[4] { 0x6C, 0x6F, 0x76, 0x65 }` となります。
整数に直すと `1,819,244,133` です。

署名は秘密鍵での暗号化なので `平文 ^ privateExponent mod modulus` の式で行います。
今回は `1,819,244,133 ^ 2,281,334,485 mod 3,209,141,941` です。

```c#
long plain = 1819244133;
long modulus = 3209141941;
long encrypt = 2281334485;

long result = plain;

WriteLine("{0} ^ {1} mod {2} =", plain, encrypt, modulus);
encrypt--;

while(encrypt > 0) {
    result = result * plain;
    encrypt--;
    if (result > modulus) {
        result = result % modulus;
    }
    WriteLine("( {0} x ( {1} ^ {2} mod {3} ) ) mod {3} =", result, plain, encrypt, modulus);
}

WriteLine("{0}", result);
// 1389434590
```

よって署名は `byte[4] { 0x52, 0xD1, 0x16, 0xDE }` 。
これは [openssl にて手順の確認](#openssl-にて手順の確認) の署名と一致します。
素晴らしい。

## 検証する
署名と一緒。

```cs
long encrypted = 1389434590;
long modulus = 3209141941;
long decrypt = 65537;

long result = encrypted;
Console.WriteLine("{0} ^ {1} mod {2} =", encrypted, decrypt, modulus);
decrypt--;

while (decrypt > 0)
{
    result = result * encrypted;
    decrypt--;
    if (result > modulus)
    {
        result = result % modulus;
    }
    Console.WriteLine("( {0} x ( {1} ^ {2} mod {3} ) ) mod {3} =", result, encrypted, decrypt, modulus);
}

Console.WriteLine("result = {0}", result);
// 1819244133
```

平文に戻りました。
今回はハッシュをしていないので、平文と一致すればOKですね。

## まとめ

* RSAの仕組みを理解できた。
* 高速化が必要。32bitの署名に50秒かかった。
    * `平文 ^ E mod M` は `((平文 ^ 2 mod M) ^ E/2 ) mod M` と等価であることに気づいた。これを利用すれば処理回数が N から logN になる。 50 秒が 0.02秒になった。
    
    ```c#
            long plain = 1819244133;
            long modulus = 3209141941;
            long encrypt = 2281334485;

            long result = plain;
            long outer = 1;
            var sw = new Stopwatch();
            sw.Start();
            Console.WriteLine("{0} ^ {1} mod {2} =", plain, encrypt, modulus);

            while (encrypt > 0)
            {
                if (encrypt % 2 != 0)
                {
                    outer = (outer * result) % modulus;
                    encrypt--;
                    Console.WriteLine("( {0} x ( {1} ^ {2} mod {3} ) ) mod {3} =", outer, result, encrypt, modulus);
                }
                else
                {
                    Console.WriteLine("( {0} x ( {1} ^ 2 mod {3}) ^ {2}/2 ) mod {3} =", outer ,result, encrypt, modulus);
                    result = (result * result) % modulus;
                    encrypt = encrypt / 2;
                    Console.WriteLine("( {0} x ( {1} ^ {2} mod {3} ) ) mod {3} =", outer, result, encrypt, modulus);
                }
            }

            sw.Stop();
            Console.WriteLine("result = {0}", outer);
            Console.WriteLine("time spent = {0}", sw.Elapsed.ToString());
            Console.ReadLine();
    ```
* bit数が大きくなると整数型で扱えなくなる。バイト列で計算する必要がある。
* `publicExponent` と `modulus` から `privateExponent` を導いてみたい。