id0-rsa.pubのメモ【Intro to PGP】

Intro to PGP

gpgコマンドの使い方の話。
基本的には書かれている内容に沿ってすすめるだけだが、一部不明な点があったので以下の記事も参考に進めた。 qiita.com まず鍵サーバーpgp.mit.eduでid0rsa.pub.gmailを検索するとkeyIDがA81B09D4だとわかる。

鍵サーバーから公開鍵を受信する。

$ gpg --keyserver pgp.mit.edu --recv-keys A81B09D

あとはmessage.ascとして保存したメッセージを確認して終了。

$ gpg -o out.txt -d message.asc
$ cat out.txt
Thank you Phil Zimmermann!

参考

https://qiita.com/spiegel-im-spiegel/items/079d69282166281eb946

id0-rsa.pubのメモ【Hello OpenSSL】

Hello OpenSSL

opensslコマンドの使い方の話。以下問題文。

This is an RSA key

-----BEGIN RSA PRIVATE KEY-----
MIGtAgEAAiEA5tygpSZdOZUMfuO3oTGWR4cALBtWui5UzrQw2/8JlZ0CAwEAAQIh
AI9n4Yp1KFfKlHaF8d15tgUONQXn+e3aI+beFKoi2XipAhEA/ZkHPmcDwXIqloGr
minb1wIRAOkMdv7emMGd08gwwOQ6i6sCEQC0pjcXx9BQFCCsWDDCwAC/AhEAxYcn
JQeO+izH4JpSJB/rWQIRAOO9m6JHEWgzLYD+fe003vw=
-----END RSA PRIVATE KEY-----

It was generated with the command $ openssl genrsa 256. A secret 64 bit number was encrypted with this key, resulting in this cipher text
6794893f3c47247262e95fbed846e1a623fc67b1dd96e13c7f9fc3b880642e42
Recover the secret number (in lowercase hex).

opensslコマンド

opensslコマンドの書式について以下にまとめる。[ ]内は省略可能。

openssl [サブコマンド] [オプション]

主なサブコマンド

サブコマンド 説明
ca 認証局の証明書を管理
crl CRLを管理
dgst メッセージダイジェストを計算
genrsa RSA秘密鍵を生成
md5 MD5ダイジェスト
pkcs12 PKCS#12形式のファイルの作成と管理
req X.509証明書署名要求(CSR)を管理
rsa RSA秘密鍵を管理
rsautl RSAアルゴリズムを使用したメッセージの署名、検証、暗号化および復号
s_client SSL/TLSプロトコルを使用して指定サーバに接続
s_server SSL/TLSプロトコルを使用してメッセージを受信するサーバーとして動作
version OpenSSLのバージョン情報を表示
x509 X.509証明書データを管理

公開鍵と秘密鍵の生成

opensslでは、秘密鍵と公開鍵の作成や、それらを利用した暗号化と復号が可能。
サブコマンドとして、genrsa、rsa、rsautlを利用する。

genrsa

genrsaはRSA秘密鍵を生成するサブコマンド。

openssl genrsa [オプション]

主なオプション

オプション 説明
-out <ファイル名> 生成したRSA形式の秘密鍵を出力するファイル名を指定。指定がない場合は標準出力に表示
-des 暗号化にDESを使用
-des3 暗号化にTripleDESを使用
-idea 暗号化にIDEAを使用
ビット数 生成するRSA形式の秘密鍵のビット数。指定がない場合は512ビット

rsa

rsaRSAの鍵を管理するサブコマンド。

openssl rsa [オプション]

主なオプション

オプション 説明
-in <ファイル名> 生成したRSA形式の秘密鍵のファイル名を指定。指定がない場合は標準入力から読み込む
-noout エンコードされた鍵を表示しない
-out <ファイル名> RSA形式の秘密鍵を出力するファイル名を指定。指定がない場合は標準出力に表示
-pubin <ファイル名> 生成したRSA形式の公開鍵ファイル名を指定。指定がない場合は標準入力から読み込む
-pubout 秘密鍵とペアとなる公開鍵を標準出力
-text テキスト形式で表示
-des 暗号化にDESを使用
-des3 暗号化にTripleDESを使用
-idea 暗号化にIDEAを使用

rsautl

rsautlはRSAによるメッセージの署名、検証、暗号化、復号を行うサブコマンド。

openssl rsautl [オプション]

主なオプション

オプション 説明
-decrypt ファイルの復号を行う
-encrypt ファイルの暗号化を行う
-in <ファイル名> 暗号化もしくは復号対象のファイル名を指定
-inkey <ファイル名> 秘密鍵とペアとなる公開鍵を標準出力
-out <ファイル名> 暗号化もしくは復号したファイルの内容を出力するファイル名を指定。指定がない場合は標準出力に表示
-pubin 公開鍵ファイルを入力する場合に指定

solution

長々とopensslのコマンド、オプションを書いたが、今回は与えられた秘密鍵をprivate.keyとして保存して以下のコマンドを実行すればOK。

printf "6794893f3c47247262e95fbed846e1a623fc67b1dd96e13c7f9fc3b880642e42" | xxd -r -p | openssl rsautl -inkey private.key -raw -decrypt | xxd -p -c 8 | tail -n 1

おわりに

気が向いたら証明書周りのサブコマンドも書く。

参考

2年前くらいにLPIC Level3 303 を取得したときに使っていた以下の本を参考に書きました。 www.amazon.co.jp

id0-rsa.pubのメモ【CCA on Textbook RSA】

CCA on Textbook RSA

以下問題文。

You've recovered this ciphertext being sent to a server:

912fcd40a901aa4b7b60ec37ce6231bb87783b0bf36f824e51fe77e9580ce1adb5cf894410ff87684969795525a63e069ee962182f3ff876904193e5eb2f34b20cfa37ec7ae0e9391bec3e5aa657246bd80276c373798885e5a986649d27b9e04f1adf8e6218f3c805c341cb38092ab771677221f40b72b19c75ad312b6b95eafe2b2a30efe49eb0a5b19a75d0b31849535b717c41748a6edd921142cfa7efe692c9a776bb4ece811afbd5a1bbd82251b76e76088d91ed78bf328c6b608bbfd8cf1bdf388d4dfa4d4e034a54677a16e16521f7d0213a3500e91d6ad4ac294c7a01995e1128a5ac68bfc26304e13c60a6622c1bb6b54b57c8dcfa7651b81576fc
It was encrypted with textbook RSA. The server's public key is:
-----BEGIN PUBLIC KEY-----
MIIBIjANBgkqhkiG9w0BAQEFAAOCAQ8AMIIBCgKCAQEAqalgjUvRvu7jzhFRzC0a
crh232Pkn3CqyNrlBPWRfKr3n1oWrloLj8LlWbZGj7SbZI0Clm6iMAPyCNdWtjER
LYauhV4Eguff29XpDQbVa1gSNtuam9UkLy7KgrXC+VKIUK2+eLfRg+Kx7jsuifJF
M56IBGdAoNBQSfV2o3rKqUUMUcd89bW6heVyOcKgVY7rofDmBnrTucZQCHtrNepy
64rGjABdSjikx9jUDLKRWUqDIf9sCHiBKmWag1n3Z2XNVZcVluwgGjBjjznFIwhe
E8dVnQciROpw34Tze6gTGVF2/GLHWGN4OD9aUpOwP1RDJl3451BfJ5/lYG02vPFH
+QIDAQAB
-----END PUBLIC KEY-----
The server will also decrypt any ciphertext that it's asked to, other than the original. To get the plaintext associated with a ciphertext, encode the ciphertext into the url:
https://id0-rsa.pub/problem/rsa_oracle/[message]
where the message is the ciphertext as a hex string. Recover the original message, and submit it as a lower-case hex string.

https://id0-rsa.pub/problem/rsa_oracle/[message]このURLに暗号文をくっつけて送ると復号してくれるらしい。しかし、肝心の与えられた暗号文を送ると403が返ってくるので困る。。。
与えられた暗号文をc1、平文をm1とすると、c1 = ( m1 ** e ) % Nとなる。また、公開鍵が用意されているので、平文m2を用意し、m2の暗号文をc2とすると、c2 = (m2 ** e) % Nとなる。
ここで、(c1 * c2) % Nc12としてRSAによる復号を行うと、平文m12は以下のようになる。

m12 = (c1 * c2) % N = (((m1 ** e) * (m2 ** e))**d) % N = (m1 * m2) % N

よってm1 = m12 // m2となり、与えられた暗号文の平文を求めることができる。
まず、公開鍵の中身を確認してeNを確認。

openssl rsa -text -noout -pubin -in pub.key

あとは先ほど示した手順をプログラムで書く。

import requests

def decrypt(ciphertext):
    return requests.get("https://id0-rsa.pub/problem/rsa_oracle/{}".format(ciphertext)).text

ciphertext = "912fcd40a901aa4b7b60ec37ce6231bb87783b0bf36f824e51fe77e9580ce1adb5cf894410ff87684969795525a63e069ee962182f3ff876904193e5eb2f34b20cfa37ec7ae0e9391bec3e5aa657246bd80276c373798885e5a986649d27b9e04f1adf8e6218f3c805c341cb38092ab771677221f40b72b19c75ad312b6b95eafe2b2a30efe49eb0a5b19a75d0b31849535b717c41748a6edd921142cfa7efe692c9a776bb4ece811afbd5a1bbd82251b76e76088d91ed78bf328c6b608bbfd8cf1bdf388d4dfa4d4e034a54677a16e16521f7d0213a3500e91d6ad4ac294c7a01995e1128a5ac68bfc26304e13c60a6622c1bb6b54b57c8dcfa7651b81576fc"
cipher = int(ciphertext, 16)

N = 21417796527836084184909381847347996579544574856536138887095572895605838936183797133497945149041143747935697840040038878051837066916098917830507702189036474052559440023560073044871506915412125924451079846179181310933243078160174081203833277764294560781167257508183474040791469949490073063621508350223394644084480243319785802072416191661242887403456436340352491914665462451622845195529700750590231557792010569404312659993869936897967297972271825868537334316050945924043213637990528504616783764719232801862604492419501841834817152625201356251989468366357139655821655574801663780279380761798039447128430604777726363650041
e = 65537

c1 = cipher
m2 = 3
c2 = (m2 ** e) % N

c12 = (c1 * c2) % N
m12 = int(decrypt(hex(c12)[2:]), 16)

m1 = m12 // m2
solution = hex(m1)[2:]
print(solution)

id0-rsa.pubのメモ【Insufficient Key Size】

Insufficient Key Size

以下問題文。

An incompetent systems administrator accidentally configured the company's encryption system to use very small keys. This RSA key modulus is only 119 bits.

-----BEGIN RSA PUBLIC KEY-----
MBYCD3AY9xf8ZmUVDBSIVPZMSQIDAQAB
-----END RSA PUBLIC KEY-----

Recover the decryption exponent (in lowercase hex). 

とりあえず問題文の公開鍵の中身を確認してみる。公開鍵をpub.keyで保存して以下のコマンドを実行。

$ openssl rsa -RSAPublicKey_in -in pub.key -text
Public-Key: (119 bit)
Modulus:
    70:18:f7:17:fc:66:65:15:0c:14:88:54:f6:4c:49
Exponent: 65537 (0x10001)

ここでNとeがそれぞれわかる。また、Nが119bitで極端に短いことに気づく。(以前聞いた話だと512bitくらいまでならお手持ちのパソコンで簡単に素因数分解可能だったはず)
計算しやすいようにNをintに直して素因数分解する。(:を取り除いたものを10進数に直す)

$ python
>>> modulus = int("70:18:f7:17:fc:66:65:15:0c:14:88:54:f6:4c:49".replace(":", ""), 16)
>>> modulus
582043602765817436229812959722228809

素因数分解の方法については以下のようなものがある。
* 自分でプログラムを書く
* factordbにブチ込む
* WolframAlphaにブチ込む
今回はとりあえずfactordbにブチ込んで素因数分解をした。
素因数分解できたら秘密鍵を導出して終了。

from Crypto.Util.number import inverse

p = 662700133751480051
q = 878291059745115859
N = p * q
e = 65537

phi = (p - 1) * (q - 1)
d = inverse(e, phi)
print(hex(d))

id0-rsa.pubのメモ【Ps and Qs】

Ps and Qs

以下問題文。

Here is an RSA public key and a message that's been encrypted with it.

-----BEGIN PUBLIC KEY-----
MFwwDQYJKoZIhvcNAQEBBQADSwAwSAJBAKzl5VggSXb/Jm2oqkPeRQwtpmGlLnJT
Nre4LKx3VUljtLzYWj4xoG+aHBouwJT7DyeibpasCH8Yderr4zIGTNUCAwEAAQ==
-----END PUBLIC KEY-----

message:
0xf5ed9da29d8d260f22657e091f34eb930bc42f26f1e023f863ba13bee39071d1ea988ca62b9ad59d4f234fa7d682e22ce3194bbe5b801df3bd976db06b944da


Luckily the recipient was using their random number generator incorrectly resulting in low entropy prime number generation. Here is another public key the recipient generated around the same time.

-----BEGIN PUBLIC KEY-----
MF0wDQYJKoZIhvcNAQEBBQADTAAwSQJCAPsrpwx56OTlKtGAWn24bo5HUg3xYtnz
nTj1X/8Hq7pLYNIVE57Yxoyr3zTOOBJufgTNzdKS0Rc5Ti4zZUkCkQvpAgMBAAE=
-----END PUBLIC KEY-----

Submit the secret message in lowercase hex. Some light reading material

大きな数の素因数分解は難しいが、2つの大きな数の最大公約数を求めることは容易であることを利用した問題。
2つのRSAの公開鍵に同じ素数が含まれていた場合、最大公約数を求めることで簡単にその素数がわかり、素因数分解をして秘密鍵を導出することができる。
割とCTFの問題として出題されるイメージがあり、公開鍵が2つあった場合は疑ってみると良いかもしれない。

公開鍵のパース

まず、opensslで表示した公開鍵の中身を計算に使えるようにパースする。

def parse_rsa_public_key(key):
    """Key is an RSA public-key, return the RSA modulus and exponent as ints."""
    out = subprocess.run("echo '%s' | openssl rsa -pubin -text -noout" % key, shell=True, stdout=subprocess.PIPE).stdout
    out = out.decode("utf-8")
    a = out.find("Modulus:") + len("Modulus:")
    b = out.find("Exponent")
    modulus = out[a:b]
    modulus = modulus.replace(' ', '').replace('\n', '').replace(':', '')
    N = int(modulus, 16)
    c = b + len("Exponent: ")
    d = out.find(" (0x")
    e = int(out[c:d])
    return N, e

あとはそれぞれの公開鍵をパースし、最大公約数を求め、秘密鍵を導出する。秘密鍵ができたら復号しておわり。

from math import gcd
from Crypto.Util.number import inverse
import subprocess

N1, e = parse_rsa_public_key(key1)
N2, e = parse_rsa_public_key(key2)
p = gcd(N1, N2)
q1 = N1 // p
q2 = N2 // p

phi = (p - 1) * (q1 - 1)
d = inverse(e, phi)

m = pow(message, d, N1)
solution = hex(m)[2:]
print(solution)

補足 : pycryptoは便利。

pip install pycrypto

参考

id0-rsa.pubのメモ【Cut and Paste Attack On AES-ECB】

Cut and Paste Attack On AES-ECB

ブロック暗号のモードの話。以下問題文。

ECB is the most basic mode of operation for block ciphers. When used with AES, any block of 16 bytes (the block size of AES) will encrypt to the same ciphertext when encrypted via AES-ECB with the same key. Below are 3 pairs of messages and their corresponding ciphertexts:

m1 = Deposit amount: 5 dollars
c1 = 0x5797791557579e322e619f12b0ccdee8802015ee0467c419e7a38bd0a254da54
m2 = One million dolls is quite the collection
c2 = 0xb1e952572d6b8e00b626be86552376e2d529a1b9cafaeb3ba7533d2699636323e7e433c10a9dcdab2ed4bee54da684ca
m3 = Hey nice binoculars
c3 = 0x35d0c02036354fdf6082285e0f7bd6d2fdf526bd557b045bce65a3b3e300b55e

Let's suppose there is a (very very bad) protocol to communicate with your bank out there that works as follows: All correspondence is encrypted via AES-ECB and everyone shares a unique key with the bank. The bank will assume all messages are from you provided they decrypt under your key. Suppose you observed the above three ciphertexts being sent to the bank and know their corresponding messages. What ciphertext would you send the bank to forge the message "Deposit amount: One million dollars"? Submit your solution in lowercase hex, no leading 0x.

ブロック暗号は平文を固定のブロック長に分割して暗号化する。しかし、そのままだとブロック長より長い平文を暗号化できない。そこで、暗号化モードという仕組みにより任意の長さの平文を暗号化している。ECBモードは最も単純な仕組みの暗号化モードで、同一の平文ブロックをECBモードで暗号化すると、同一の暗号文ブロックが出力されるという問題がある。
まず入力となる平文を16バイトずつに区切ってみる。
m1はDeposit amount:+5 dollars
m2はOne million doll+s is quite the c+ollection
m3はHey nice binocu+lars
すると、今回作るDeposit amount: One million dollarsという文字は、m1(Deposit amount:)、m2(One million doll)、m3(ars)にそれぞれ存在していることがわかる。
あとはそれに対応する暗号文をくっつけてsubmitして終了。 5797791557579e322e619f12b0ccdee8b1e952572d6b8e00b626be86552376e2fdf526bd557b045bce65a3b3e300b55e

id0-rsa.pubのメモ【Caesar】

Caesar

シーザー暗号の話。以下問題文。

Should probably stick to the salad 

ZNKIGKYGXIOVNKXOYGXKGRREURJIOVNKXCNOINOYXKGRRECKGQOSTUZYAXKNUCURJHKIGAYKOSZUURGFEZURUUQGZZNKCOQOVGMKGZZNKSUSKTZHAZOLOMAXKOZYMUZZUHKGZRKGYZROQKLOLZEEKGXYURJUXCNGZKBKXBGPJADLIVBAYKZNUYKRGYZZKTINGXGIZKXYGYZNKYURAZOUT

Test Vector
PT: HELLOWORLD
KEY: B
CT: IFMMPXPSME

とりあえず何文字ずらしたら良いかよくわからなかったので総当たりしてみる。

def caesar_decrypt(c, n):
  if ord('A') <= ord(c) and ord(c) <= ord('Z'):
    return chr((ord(c) - ord('A') - int(n)) % 26 + ord('A'))

def main():
  s = 'ZNKIGKYGXIOVNKXOYGXKGRREURJIOVNKXCNOINOYXKGRRECKGQOSTUZYAXKNUCURJHKIGAYKOSZUURGFEZURUUQGZZNKCOQOVGMKGZZNKSUSKTZHAZOLOMAXKOZYMUZZUHKGZRKGYZROQKLOLZEEKGXYURJUXCNGZKBKXBGPJADLIVBAYKZNUYKRGYZZKTINGXGIZKXYGYZNKYURAZOUT'
  for n in range(26):
    p = ''.join((caesar_decrypt(c, n) for c in s))
    print(n, ': ', p)

if __name__ == '__main__':
    main()

なんか読めそうな文章が出てきたでのsubmitしてみたが通らない。キレそう。 THECAESARCIPHERISAREALLYOLDCIPHERWHICHISREALLYWEAKIMNOTSUREHOWOLDBECAUSEIMTOOLAZYTOLOOKATTHEWIKIPAGEATTHEMOMENTBUTIFIGUREITSGOTTOBEATLEASTLIKEFIFTYYEARSOLDORWHATEVERVAJDUXFCPVUSETHOSELASTTENCHARACTERSASTHESOLUTION Discuss The Problemをみると、テキストを読めみたいなことが書いったので読んで指示通りsubmitすれば終了。(めんどくさい)

Read the text that your decryption yields and follow the instructions, that will lead you to the solution we're looking for.