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

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

~~.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) で確認しながら実行していったのでメモとして掲載。

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

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=

base64をdecodeする。

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

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

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

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

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 }

コンテンツをパースする

構造は次のように定義されている。
```
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 は存在しない。
2. ID: 2(Int), Length: 5, Contents: byte[5] { 0, 191, 71, 158, 181 } = modulus: 3,209,141,941
3. ID: 2(Int), Length: 3, Contents: byte[3] { 1, 0, 1 } = publicExponent: 65,537
4. ID: 2(Int), Length: 5, Contents: byte[5] { 0, 135, 250, 102, 213 } = privateExponent: 2,281,334,485
5. ID: 2(Int), Length: 3, Contents: byte[3] { 0, 248, 111 } = prime1: 63,599
6. ID: 2(Int), Length: 3, Contents: byte[3] { 0, 197, 27 } = prime2: 50,459
7. ID: 2(Int), Length: 2, Contents: byte[2] { 41, 131 } = exponent1: 10,627
8. ID: 2(Int), Length: 2, Contents: byte[2] { 106, 253 } = exponent2: 27,389
9. 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 です。

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 にて手順の確認の署名と一致します。
素晴らしい。

検証する

署名と一緒。

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秒になった。

        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 を導いてみたい。