namdicul's blog

気ままに更新します. CTFについて勉強中です.

暗号理論(2) 〜 共通鍵暗号方式 〜

続いては, 共通鍵暗号方式について説明したいと思います. 



暗号方式には主に「共通鍵暗号方式」と「公開鍵暗号方式」に分類することができます. この記事では, 共通鍵暗号方式と公開鍵暗号方式の違いを説明し, 共通鍵暗号方式の代表的な例であるXORを用いた暗号方式, 使い捨てパッド(ワンタイムパッド), DESなどについて説明していこうと思います.

共通鍵暗号方式

共通鍵暗号方式とは, 暗号化と復号化に同じ鍵を用いることです. データの送信者と受信者が同じ鍵を持つことで簡単に共通鍵暗号方式を実現することができます.

f:id:tomonori4565:20180521155637j:plain
共通鍵暗号方式の概略図

共通鍵暗号方式は実現が簡単で運用しやすいのがメリットですが, もしこの共通鍵がデータのやり取りをする以外の者に知られてしまった場合, 簡単に復号化されてしまいます. また, データのやり取りをする両者が事前に共通鍵を共有できていればいいのですが, 実際にデータのやり取りをする人は面識のない人であることが多いです. よって, やり取りをする相手に共通鍵を渡さなければいけないのですが, その共通鍵をそのままネット上で渡そうとすると, 他者に鍵が知れ渡ってしまいます. このように共通鍵暗号方式では, 鍵配送問題が生じてきてしまいます.

公開鍵暗号方式

公開鍵暗号方式は, 暗号化と復号化で違う鍵を使用する暗号方式です.

f:id:tomonori4565:20180521155735j:plain
公開鍵暗号方式の概略図

公開鍵暗号方式では, 暗号化するための鍵(公開鍵)は全員に公開します. つまり公開鍵は誰でも入手することができます. しかし, 復号化するための鍵(秘密鍵) は復号化する人しか持ってはいけません. こうすることで, 共通鍵暗号方式のときに生じた鍵配送問題が解決されます.

XORによる共通鍵暗号方式の実現

ここでは, XOR(排他的論理和)を共通鍵として用いた共通鍵暗号方式を考えます.

XORとは演算子の1つで, 以下のような計算をします.


0 XOR 0 = 0
0 XOR 1 = 1
1 XOR 0 = 1
1 XOR 1 = 0

例えば, 01001100 XOR 10101010の計算結果は, 「11100110」になります.


ここで, 平文Aをビット列01001101, 共通鍵keyをビット列11110000とします. Aとkeyを用いて暗号文Bを計算してみると,


A XOR key = 01001101 XOR 11110000 = 10111101

つまり, B=10111101となりました. これで暗号化は完了です.


では, 復号化する場合はどのようにすれば良いでしょうか.




実は, B XOR keyを計算することによって, 平文Aを得ることができます.


B XOR key = 10111101 XOR 11110000 = 01001101

このように, 平文A=01001101を復元することができました.




以上のように, XOR演算を用いることで, 共通鍵暗号方式を実現することができます.

絶対に解読できない使い捨てパッド(ワンタイムパッド)

タイトルをみてびっくりされた方も多いのではないでしょうか. 暗号理論の世界では, 絶対に解読できない「使い捨てパッド(ワンタイムパッド)」というものが存在します.


使い捨てパッドとは, XOR演算を用いた暗号化方式です. 先ほどと同様のことを実行するので, そこまで複雑ではありません.

まず, "onetime"という平文Aを使い捨てパッドを用いて暗号化してみようと思います. まず, "onetime"という文字列をASCIIコードに直します.


A = 01101111 01101110 01100101 01110100 01101001 01101101 01100101

ここで, 使い捨てパッドの鍵keyを以下のように定義します.


key = 00011111 00001111 00001001 00010011 00000011 00001001 00010010

すると, 暗号文Bは以下のように計算できます.


B = A XOR key = 01110000 01100001 01101100 01100111 01101010 01100100 01110111

このBを文字列に直すと, "palgjdw"となります.


ではいま, 暗号文Bだけが与えられている状況を考えます. もちろん, keyやAは知りません.
このとき, 元の平文Aを得るためにはどのようなことをすれば良いでしょうか.


この前の記事でブルート・フォース・アタックについては説明しました. 今回もこの解読方法を使えば(かなり時間はかかりますが)復号できそうです. 試してみましょう.



例えば, key = 00011011 00000100 00010101 00010000 00000101 00010110 00010011として, B XOR keyを計算して, 平文Aを求めると,
A = 01101011 01100101 01111001 01110111 01101111 01110010 01100100 となり, これを文字列に直すと"keyword"という意味のある平文が得られました.

ということで, 今回ブルート・フォース・アタックが成功しました...




という風にはならないのです.

もともと平文Aはonetimeでしたよね. ですので今回の場合は復号失敗となってしまうのです.


使い捨てパッドは, ブルート・フォース・アタックによっていつかは元の平文Aを得ることができます. しかしいくら復号したとしても, どの場合が復号成功がわからないのです. なので, 使い捨てパッドは絶対に解読できないのです.


ピンと来ない方もいると思うので, もう少し説明しましょう.

先ほどの例で, key色々変えていくことによって, 7文字の文字列をたくさん生成することができます. 例えば, "morning", "evening", "goodbye"といった英単語を得ることができるし, "abcdefg", "fffffff"といった規則正しい文字列も得ることができます. これらは全て「意味のある文字列」の可能性があります. なので, 一意にこれといった復号化をすることが絶対にできないのです.


こういった意味で使い捨てパッドは理論的に解読不可能なわけです.

使い捨てパッドが使われない理由

では, 全ての暗号化方式に使い捨てパッドを利用すればいいではないかという疑問が生まれます.
実は, 使い捨てパッドには非常にデメリットが多いのです.


1. 鍵配送問題
共通鍵暗号方式には鍵配送問題はつきものです.
いくら暗号文から元の平文を絶対に復号できないとしても, 鍵自体がバレてしまったら元も子もないわけです. 鍵を安全に相手に送る方法が必要なわけです.

2. 鍵の保存問題
もし鍵をしっかり保存できるのであれば, もともと暗号化方式など必要ないですよね. だって平文も同じように管理すれば良いのですから.

3. 鍵の再利用
「使い捨て」とあるように, 使い捨てパッドは再利用できません. 再利用すると, 過去に行った通信内容がバレてしまいます.

他にも, 「鍵の同期」, 「鍵の生成」問題などがあります.

DES (Data Encryption Standard)

DESは, 世界中の政府や銀行などで広く用いられてきた共通鍵暗号方式です. しかし, 現在では使用されていません. ブルート・フォース・アタックで解読されてしまうためです.

DESの暗号化と復号化

f:id:tomonori4565:20180608222838j:plain
DESの全体像

DESは, 64ビットの平文を56ビットの鍵を用いて64ビットの暗号文に暗号化するアルゴリズムです. 復号化するときも同様で, 同じ鍵を利用して64ビットの平文に復号化します.

先ほど, 鍵は56ビットと言いましたが, 規格上は64ビットとなっています. これは, 誤り検出のビットが7ビットおきに入っているからです.


DESは, 64ビットの平文をまとめて暗号化します. このまとまりのことを「ブロック」と言います.
DESのように, ブロック単位で暗号化と復号化をする暗号アルゴリズムのことを「ブロック暗号」といいます.

平文が64ビット以上ある場合は, 平文をブロック単位に分割してそれぞれを暗号化することになります. この繰り返して暗号化する方法のことを「モード」と言います.

Feistel network(ファイステルネットワーク)とは

DESはファイステル構造という基本構造をなしています.

f:id:tomonori4565:20180608224804p:plain
ファイステル構造

ファイルテルネットワークでは, 暗号化のステップ(これをラウンドと言います)を何度も繰り返す仕組みを取っています. DESでは, ラウンドを16回繰り返すことになっています.


ここで, ファイステルネットワークについて解説していきたいと思います. 手順は以下の通りです.

ファイステルネットワークにおける暗号化

(1) 64ビットの入力を半分に分割し, 右と左に分ける.
それぞれ32ビットずつになります.

(2) 右をそのまま暗号文(右)に送る.
何も暗号化する必要はありません.

(3) 右をラウンド関数に送り, サブ鍵を用いて暗号処理をし, 出力する.
具体的には, 32ビットの右を48ビットに拡大し, サブ鍵とXORを取ります. この結果48ビットのXOR暗号文を8つのSボックス(それぞれ6ビット)に分割し, 6ビットを4ビットに縮小することによって32ビットの出力を計算します(これについては, また機会があるときに詳しく説明したいと思います).

(4) fの出力と平文の左のXORを取ることによって暗号文(左)を計算する.



この(1)から(4)の流れが1ラウンドとなります. これを16回繰り返すわけですが, このままだと右は暗号化されないことになってしまいます. これではまずいですね.

ですので, 2ラウンド目の入力は, 1ラウンド目の出力の左右を入れ替えたものを入力します. 同様に3ラウンド目の入力は, 2ラウンド目の出力の左右を入れ替えたものを入力し, 4ラウンド目の入力は, 3ラウンド目の出力の左右を入れ替えたものを入力します.

ファイステルネットワークにおける復号化

では復号化はどうやればいいのでしょうか.

実は, 暗号化と全く逆のことをしてやればOKです.


なぜこれで良いのかというのは, XORの性質を考えると当然ですね.

ファイステルネットワークの性質

(1) 好きなだけラウンド数を増やすことができる.

(2) ラウンド関数fにどんな関数を使っても復号化である.

(3) 暗号化と復号化が同じ構造で実現できる.

暗号理論 (1) 〜 古典的暗号 〜

こんにちは.

今日は暗号理論を語るにあたって, 知っておくべき古典的暗号について紹介します. また, その暗号解読法について紹介していきたいと思います.

シーザー暗号 (Cither cryptography)

まず一番単純なシーザー暗号について紹介していきたいと思います.
シーザー暗号では, 元々の平文のアルファベットを決められた文字数分(この値をkeyと定義します)だけずらすという暗号方式です. ここで具体例を見てみましょう.

f:id:tomonori4565:20180521140331j:plain
Cither cryptography

(補足と謝罪:画像に少しミスがあります. 画像右側の矢印, 1つずつずれてますね...申し訳ないです.)

例えば, "hatenablog"をシーザー暗号によって暗号化してみましょう. ここではkey=3, つまり3文字分ずらしてみましょう.
すると,


h → k
a → d
t → w
.
.
.
o → r
g → j

となり, 暗号文は"kdwhqdeorj"となるわけです.

次に, シーザー暗号で暗号化された暗号文を復号化してみましょう. どうすればいいでしょうか考えてみてください.




key=-3として3文字分逆にずらしてやればOKですね. つまり,


k → h
d → a
w → t
.
.
.
r → o
j → g

とずらしてやり, 復号文(つまり平文)は"hatenablog"となるわけです.



いかかでしょうか. シーザー暗号はとても単純な暗号方式であることがわかりますね.




ではここで話を少し変えてみましょう.

あなたは盗聴者です. あなたはAさんからBさんのデータのやり取りを盗聴し, そのデータの内容を取得しようと思っています. しかし, データは暗号化されており, 内容を知ることはできません. 取得した暗号文は"spwwzhzcwo"であることがわかりました. あなたならデータの内容を取得する(つまり暗号文を解読する)ために何をするでしょうか.




一番有効なのは, 暗号文をシーザー暗号だと仮定し, keyを-1, -2, ..., -25, -26とずらしていき, 意味のある復号文を得ようとすることです.
実際にやってみましょう.

-26 shift: spwwzhzcwo
-25 shift: tqxxaiadxp
-24 shift: uryybjbeyq
-23 shift: vszzckcfzr
-22 shift: wtaadldgas
-21 shift: xubbemehbt
-20 shift: yvccfnficu
-19 shift: zwddgogjdv
-18 shift: axeehphkew
-17 shift: byffiqilfx
-16 shift: czggjrjmgy
-15 shift: dahhksknhz
-14 shift: ebiiltloia
-13 shift: fcjjmumpjb
-12 shift: gdkknvnqkc
-11 shift: helloworld
-10 shift: ifmmpxpsme
-9 shift: jgnnqyqtnf
-8 shift: khoorzruog
-7 shift: lippsasvph
-6 shift: mjqqtbtwqi
-5 shift: nkrrucuxrj
-4 shift: olssvdvysk
-3 shift: pmttwewztl
-2 shift: qnuuxfxaum
-1 shift: rovvygybvn

「-11 shift」を見ると, "helloworld"という意味のある文章を得られましたね.

このように, 全ての鍵の候補を試してみるという暗号解読方法をブルート・フォース・アタックと言います.

シーザー暗号に関しては, ブルート・フォース・アタックによって簡単に暗号文を解読することができます. よってシーザー暗号は秘密データを守るには弱すぎることがわかりますね.

では, ブルート・フォース・アタックによって解読されにくい強い暗号化方式は存在しないのでしょうか.

存在します. 次に紹介する単一換字暗号という暗号方式はブルート・フォース・アタックによって解読されにくいです.


以下は, 自作したシーザー暗号の暗号化・復号化ツールです. よかったら利用してみてください.

print('***Cither cryptography***\n')

print('Input message below.')
message = input()
message_list = list(message)

print('\n')

for i in range(1, 27):
    return_message = ''
    for element in message_list:
        if (ord(element) + i) <= 122:
            return_message += chr(ord(element) + i)
        else:
            return_message += chr(ord(element) + i - 26)
            print('{0} shift: {1}'.format(i, return_message))

print('\n****************************\n')

for i in range(-26, 0):
    return_message = ''
    for element in message_list:
        if (ord(element) + i) >= 97:
            return_message += chr(ord(element) + i)
        else:
            return_message += chr(ord(element) + i + 26)
    print('{0} shift: {1}'.format(i, return_message))

単一換字暗号 (simple substitution cipher)

単一換字暗号とは, アルファベット上の文字からアルファベット上の文字に対して, 1対1の対応関係を持たせて暗号化する方式です.

f:id:tomonori4565:20180521145354j:plain
simple substitution cipher

上の画像のように, 元のアルファベットと暗号先のアルファベットの対応関係を表した表のことを換字表と言います.

自作したプログラムを元に単一換字暗号を実際に実行してみましょう.

import random

print('***Single substitution***\n')

print('Input message below.')
message = input()
message_list = list(message)
alphabet_list = list('abcdefghijklmnopqrstuvwxyz')
print(alphabet_list)

random.shuffle(alphabet_list)

print(alphabet_list)

return_message = ''
for element in message_list:
    return_message += alphabet_list[ord(element) - 97]

print(return_message)

print('\n****************************\n')

以下は実行結果です.

***Single substitution***

Input message below.
hatenablog

['a', 'b', 'c', 'd', 'e', 'f', 'g', 'h', 'i', 'j', 'k', 'l', 'm', 'n', 'o', 'p', 'q', 'r', 's', 't', 'u', 'v', 'w', 'x', 'y', 'z']
['a', 'g', 'f', 'v', 'p', 's', 'i', 'n', 'l', 'c', 'k', 'j', 'o', 'd', 'u', 'z', 'w', 'r', 'e', 'b', 'q', 'x', 'y', 'm', 't', 'h']
nabpdagjui

****************************

いま, "hatenablog"という平文を単一換字暗号で暗号化しています. 換字表は2つのリスト構造で表現されています.

つまり,


h → n
a → a
t → b
.
.
.
b → g
l → j
o → u
g → i

というように暗号化しています. 結果的に, 暗号文は"nabpdagjui"になっていることがわかりますね.



復号化するには, 暗号化に用いた換字表を用いて, 逆変換してやればOKです.





では, シーザー暗号のときと同じ質問をします.

あなたは盗聴者です. あなたはAさんからBさんのデータのやり取りを盗聴し, そのデータの内容を取得しようと思っています. しかし, データは暗号化されており, 内容を知ることはできません. 取得した暗号文は"spwwzhzcwo"であることがわかりました. あなたならデータの内容を取得する(つまり暗号文を解読する)ために何をするでしょうか.


先ほど学んだブルート・フォース・アタックを実行しようと考えた方もいるかもしれません. しかしよく考えてみてください.


シーザー暗号のときは, 鍵の候補は26通りしか存在しなかったので, ブルート・フォース・アタックによって簡単に暗号解読をすることができました. では, 単一換字暗号の場合はどうでしょうか.


最大26!通り存在することがわかります. 26! = 1×2×3×...×25×26=403291461126605635584000000なので, 全ての鍵を試すことは実質不可能であることがわかります.


では, 単一換字暗号は一生解読することができないのでしょうか.

実はそういう訳でもありません. 一度, 解読方法を考えてみてください.





単一換字暗号を解読するには, 「頻度分析」というものを使うのがよさそうです.


アルファベットは, どの文字も等確率で現れる訳ではなく, 多少偏りを持って出現します. xの出現確率とaの出現確率は, 直感でも違うことがわかりますね. このように, 暗号文に出てくる文字の出現頻度を分析して, 平文に直す作業のことを頻度分析というのです.


英語の文章では, e, t, a, o, i, n, s, ... という順に出現頻度が小さくなっていきます. もし, 暗号文にwの文字が多く出現している場合は, 元の文字がeやtやaである確率が高い訳です. そのようにして暗号文を復号化していくのです.



いずれにせよ, シーザー暗号のブルート・フォース・アタックに比べて, 骨の折れる作業であることは間違い無いですね.


エニグマ (Enigma)

編集中です.すいませんm(__)m

RSA暗号 ~まとめ~

お久しぶりです.

最近CTFの勉強をしていて, RSA暗号に触れる機会があったのでまとめておこうと思います. 出来るだけほかの人にもわかりやすく書いていこうと思います. 
昨年授業でRSA暗号については一通り習ったのですが, やはり1年も経つと忘れてましたね...これを機にもう一度覚えなおしていきたいと思います.

この記事を作るにあたって, 以下のサイトには大変お世話になりました. 本当にありがとうございました.
mathtrain.jp

tsujimotter.hatenablog.com

RSA暗号とは

RSA暗号とは, 公開鍵暗号方式を利用した暗号方法です. 暗号方式には共通鍵暗号方式と公開鍵暗号方式というものが存在します. RSA暗号ではそのうち公開鍵暗号方式を利用しているんですね.
RSA暗号を理解するには, 高校数学で1通り学ぶ初等整数論を理解している必要があります. 合同式を利用するので, 合同式を用いた計算は1通りできておいたほうが良いと思います. またフェルマーの小定理というものを途中で使用するのですが, これは大学の数学で学ぶことなので, 紹介はしますが証明まではしません. 詳しい証明が知りたい人は個人で調べてもらえるとありがたいです.

そもそも暗号化とは?

これは説明するまでもないと思いますが, 暗号化とはデータの内容を他人にはわからないようにするための方法です. 例えば, オンラインショッピングをするとき, クレジットカードのカード番号がそのままネットワーク上に流れてしまったらどうなるでしょうか. 当然そのデータが盗聴されてしまったらカードが不正利用されてしまい, 大変なことになってしまいますよね. そのため, 見られたくないデータをネットワークを通してやり取りする場合は, 暗号鍵を利用して暗号化をしなければいけません.
また暗号化したら, 復号化出来なければいけません. 暗号化したまま復号化出来なければ, もとのデータは利用できなくなってしまい,本末転倒ですね. なので, 復号鍵を利用して暗号化データをもとのデータに直してやる必要があります. もし暗号鍵と復号鍵が同じである場合は「共通鍵暗号方式」, 違う場合は「公開鍵暗号方式」といいます. つまり, RSA暗号では暗号鍵と復号鍵は別のものであるということです.

f:id:tomonori4565:20180514222943j:plain
f:id:tomonori4565:20180514222910j:plain

RSA暗号の仕組み

平文(暗号化する前のデータ)をP, 暗号文をCとします. また2つの暗号鍵(公開鍵なので他人に知られても大丈夫)をk, mとします. ここで, 平文 Pから暗号文 Cを得る暗号化方法は以下の通りです.


P^{k} \equiv C (mod ~ ~ m) ~~~ ... (1)

つづいて, 暗号文 Cから平文 Pを得る復号化方式は以下の通りです. ここで,  uとは復号鍵のことを指します. 復号鍵は秘密鍵なので, 他人に知られてはいけません.


 C^{u} \equiv P (mod ~ ~ m) ~~~ ... ~(2)


ここで(1), (2)から


P^{ku} \equiv P (mod ~ ~ m) ~~~ ... ~(3)

となります. つまり, (3)を満たすような復号鍵 uが存在すれば復号化することができます.
このあとも説明しますが, 実はこのような復号鍵は存在するのです. しかし, この復号鍵を公開鍵 k, mから計算して導出することは現実に難しいです(理論的に不可能ではないのですが, 計算する時間が膨大になってしまいます). つまり, 暗号文を復号するのは復号鍵 uを知っている人にしかできないという仕組みになっているのです.

RSA暗号の仕組み(さらに詳しく)

RSA暗号の公開鍵は2つ存在しますが( k, mの2つ), そのうち mは非常に大きい素数 p, qを用いて,


 m = pq ~~~

となります. 先ほど復号鍵は秘密鍵なので知られてはいけないといいましたが, 実はこの p, qも他人に知られてはいけません. ここもポイントなのですが, こうすることによってRSA暗号の安全性と信頼性が担保されることになるのです(のちに詳しく説明します).


さてここから, なぜRSA暗号がうまく機能するのか説明していこうと思います.

復号鍵の一意存在性

ここでオイラーの定理 というものを使用します. オイラーの定理このサイトを利用して説明を省略しようと思います.

オイラーの定理を使用すると,  P, mは互いに素なので,


 P^{\varphi(m) \cdot v} \equiv 1 (mod ~ ~ m) ~~~ ... ~(4)

となります( vは整数).
(4)を少し変形します. 両辺に Pをかけると,


 P^{\varphi(m) \cdot v + 1} \equiv P (mod ~ ~ m) ~~~ ... ~(5)

となります. ここで(3)と指数部を比較してみましょう. すると,


 k \cdot u = \varphi(m) \cdot v + 1 ~~~ ... ~(6)

となります.
細かいですが, さらに変形して,


 k \cdot u -  \varphi(m) \cdot v = 1 ~~~ ... ~(7)

さて, ここまで色々な式変形をしてきましたが, ここで知りたいことはタイトルにもあるように「復号鍵が一意に存在するか」ということです. つまり(7)を満たすような整数 u, vが存在すればOKです.


ここで高校数学を思い出しましょう. 以下の定理, 覚えているでしょうか.

「一次不定方程式の整数解」

 a, bを互いに素な整数としたとき,  au + bv = 1を満たすような整数解 u, vが存在する.

これを(7)に適用してみましょう. いま k, \varphi(m)が互いに素であるならば, (7)を満たすような整数 u, vが存在します. 整数 kは何を選んでもよいので, 素数を選んでしまえばOKそうですね.
このことから復号鍵は一意に存在することが示せました.


(補足)少し複雑な説明は省略してしまいましたが,  u, vは複数の解をもちます. そのうち,  uが正となるものを選んであげてください.


他人が復号鍵を計算することの困難性

復号鍵が一意に存在することはわかりましたが, もし k, mから復号鍵が生成できてしまったらどうでしょう. 暗号化する意味がなくなってしまいますよね. ここでは, 復号鍵も持たない他人が復号鍵を生成することができるのかということを説明していきたいと思います.

もう一度(7)の式を見てみましょう.( k, mは既知なのでということを忘れないでください). もし \varphi(m)が計算できてしまったら復号鍵が生成できてしまいます. でも, すでに mは既知だから,  \varphi(m)は簡単に計算できてしまうんじゃないの?と思う方もいるかもしれません.



ここで少し前に説明したことを思い出してほしいのです.

RSA暗号の公開鍵は2つ存在しますが( k, mの2つ), そのうち mは非常に大きい素数 p, qを用いて,


 m = pq

となります.

そして,  \varphi(m)は以下のように計算することができます.


\varphi(m) = (p - 1)(q - 1) ~~~ ... ~(8)

もし仮に p, qの値を事前に知っていないのならば,  m素因数分解しなければなりません. しかし,  p, qは非常に大きな素数なので, 素因数分解するには膨大な時間がかかってしまうのです. なので先ほども言いましたが,  p, qは他人に知られてはいけないのです. ここがミソなんです.


すなわち, 暗号化したデータを復号化できるのは,

  • 復号鍵 uを保持している人(つまり p, qの値を知っている人)

に限られてくるのです.



このようにしてRSA暗号の安全性を担保することができるのです.


まとめ

分かりやすかったでしょうか. RSA暗号は美しい数学的性質をうまく利用した暗号化方式であることがわかりましたね.
しかし, 今後量子コンピュータなどが登場した場合,  mを簡単に素因数分解できてしまう可能性も否めません. 時代に即した暗号化方式を適用する必要がありますね.

"Cpaw CTF" Q29.[Crypto] Common World

Cpaw君は,以下の公開鍵を用いて暗号化された暗号文Cを受け取りました.しかしCpaw君は秘密鍵を忘れてしまいました.Cpaw君のために暗号文を解読してあげましょう. 

(e, N) = (11, 236934049743116267137999082243372631809789567482083918717832642810097363305512293474568071369055296264199854438630820352634325357252399203160052660683745421710174826323192475870497319105418435646820494864987787286941817224659073497212768480618387152477878449603008187097148599534206055318807657902493850180695091646575878916531742076951110529004783428260456713315007812112632429296257313525506207087475539303737022587194108436132757979273391594299137176227924904126161234005321583720836733205639052615538054399452669637400105028428545751844036229657412844469034970807562336527158965779903175305550570647732255961850364080642984562893392375273054434538280546913977098212083374336482279710348958536764229803743404325258229707314844255917497531735251105389366176228741806064378293682890877558325834873371615135474627913981994123692172918524625407966731238257519603614744577) 

暗号文: 80265690974140286785447882525076768851800986505783169077080797677035805215248640465159446426193422263912423067392651719120282968933314718780685629466284745121303594495759721471318134122366715904 

これは…? 

フラグは以下のシンタックスです. 
cpaw{復号した値} 

※復号した値はそのままで良いですが,実は意味があります,余力がある人は考えてみてください

Answer:

 

今回はRSA暗号を使って暗号化したものを復号するのが目的です. 

その前に, RSA暗号について理解が曖昧だったので, まずRSA暗号について説明したいと思います. 

 

以下, Wikipediaから引用.

RSA暗号は次のような方式である: 鍵ペア(公開鍵と秘密鍵)を作成して公開鍵を公開する。まず、適当な正整数 e(通常は小さな数。(65537 = 216 + 1) がよく使われる)を選択する。また、大きな2つの素数 {pq} を生成し、それらの積 n (=pq) を求めて、{en} を平文の暗号化に使用する鍵(公開鍵)とする。2つの素数 {pq} は、暗号文の復号に使用する鍵(秘密鍵d の生成にも使用し ()、秘密に保管する。

  • 暗号化(平文 m から暗号文 c を作成する): 
  • 復号(暗号文 c から元の平文 m を得る): 

ここで、暗号化(e 乗)は、{en } があれば容易に計算できるのに対して、復号(e 乗根)は、「n の素因数を知らないと難しい(大きい合成数素因数分解も難しい)」と考えられている。つまり秘密鍵を用いずに暗号文から平文を得ることは難しい、と信じられている。これがRSA暗号の安全性の根拠である。

 また, RSA暗号についてはここでも簡潔に説明されています.  

 

 RSA暗号については後々別の記事で説明したいと思いますが, こちらのプログラムとこちらの解説記事が参考になりそうですね. 

"Cpaw CTF" Q26.[PPC]Remainder theorem

x ≡ 32134 (mod 1584891) 
x ≡ 193127 (mod 3438478) 

x = ? 


フラグはcpaw{xの値}です!

 

Answer:

 

プログラムを組みましょう. 今回はC言語を用いてプログラムを作成しました.

久しくプログラムを書いていなかったので, 最初は勘が鈍っていたのでしょうか...まさかの1から順にインクリメントしていきながらxの条件に合っているかを確かめていました...クソ非効率でしたね...

 

以下は作成したプログラムです. 参考にしてください.

#include <stdio.h>

 

int main()

{

 

  unsigned long i;

  for(i = 193127 ;; i+=3438478){

    if(i % 1584891 == 32134){

      printf("FLAG is -----------------> cpaw{%lu}\n", i);

      break;

    }

 

    printf("i = %lu is \t\t\t\t\t\t NO!!\n", i);

  }

 

  return 0;

}

 

"Cpaw CTF" Q24.[Web]Baby's SQLi - Stage 2-

うーん,ぱろっく先生深くまで逃げ込んでたか. 
そこまで難しくは無いと思うんだけども……. 

えっ?何の話か分からない? 
さてはStage 1をクリアしてないな. 
待っているから,先にStage 1をクリアしてからもう一度来てね. 

Caution: sandbox.spica.bzの80,443番ポート以外への攻撃は絶対にしないようにお願いします.

 Answer:

 

これは授業で習ったので解法は結構すぐ思いつきました(^^).

SQLインジェクション」を用いた問題ですね. 

passwordには, 

\'' OR 1=1 --'

を入力してやればOKですね. 

"Cpaw CTF" Q23.[Reversing]またやらかした!

またprintf()をし忘れたプログラムが見つかった。 
とある暗号を解くプログラムらしい… 
reversing200

 Answer:

 

今回はかなり書くことが多そうです. 勉強になったので細かくわかりやすく書いていこうと思います. 

さて, Reversing問題なのでとりあえずファイルをダウンロードしてfileコマンドでどんな種類のファイルなのかを調べます. すると前回と同様ELF形式であることがわかったので, 実行権限を与えて実行してみます. 今回は何も表示されませんでした. 

 

前回同様にstringsコマンドを使ったり, ltraceコマンド, straceコマンドを実行してもflagは得られそうにありませんでした. そこで使用したのは「gdbデバッグ」です. 

 

実は僕もgdbデバッグはそんなに使用したことがなかったので, 今回はflagを得るのに非常に苦労しました. こちらのサイトを参考にさせていただきました...感謝です. 

 

 

さて, ここからgdbデバッグについて詳しく述べていこうと思います. そんなの知ってるよ!!って方は読み飛ばしてもらって構いません. 

続きを読む