隣り合うピタゴラス数の証明 Crypto CTF 2019 Alone in the dark
皆さん、こんにちは！ Ken.Sです！
今回はCTFというコンピュータセキュリティ技術を競うコンテストのある一問の解法を書いてみました。基本的にはこのサイトと言っていることは同じなのですが、途中いくつか解説を飛ばしているのでそれを加えていきたいと思います。
Crypto CTF write up（供養） - Qiita
与えられたファイルはこの二つです。
We are alone in the dark with a single line!
とりあえずpythonファイルを読んでみましょう。
u,v,x,yをstr型にしてハッシュにしたのが今回のフラグのようです。さてその4つの変数のヒントにassertで複雑な式が書いてあります。
よく見ると、A^2 + B^4 + C^6 + D^8 + E^10 + F^12 = 64という式になりますね。直感的にE,Fは0になりそうな気がします。A~Fは全て偶数乗するので正の値になります。ではプログラムを組んでこの式が成り立つA~Fを求めてみましょう。
見にくいプログラムで申し訳ないです…。結果より以下が考えられます。
- A = 8, 他は0 ・・・(p)
- C = 2, 他は0 ・・・(q)
ではこの2パターンp,qについて解いていきます。
パターンpの場合
A : u^2 + (u+1)^2 - v^2 = 8
これを満たす整数u,vはあり得そうですね。同様に考えると
B : (x+1)^3 - x^3 - y^2 = 0
C : gmpy2.is_prime(v)+1 = 0
おっと。ここで問題がありました。gmpy2.is_prime(v)はvが素数なら1を返し、そうでないなら0を返します。となるとCは1,もしくは2となります。故にパターンpは成り立たないことが分かりました。
パターンqの場合
A : u^2 + (u+1)^2 - v^2 = 0
B : (x+1)^3 - x^3 - y^2 = 0
C : gmpy2.is_prime(v)+1 = 2
D : gmpy2.is_prime(y)-1 = 0
E : len(bin(u)[2:])-664 = 0
F : len(bin(x)[2:])-600 = 0
これは全て成り立ちますね。
言い換えるとこうなります。
A : u^2 + (u+1)^2 = v^2
B : 3x^2 + 3x + 1 - y^2 = 0
C : vは素数
D : yは素数
E : uは2進数表記で664桁 ※bin(u)[0:2] = 0b
F : xは2進数表記で600桁
方針を以下のようにします。
- Aを満たすu,vを見つけ、それらがC,Eを満たすなら出力する
- Bを満たすx,yを見つけ、それらがD,Fを満たすなら出力する
まず方針1について解いていきましょう
A : u^2 + (u+1)^2 = v^2
これはピタゴラスの定理(三平方の定理)ですね。しかも、左辺が特殊な形、差が1の二乗の和となっていますね。これは隣り合ったピタゴラス数と呼ばれます。一番簡単なものは(3,4,5)ですね。これらは求められる式があるとのことです。
a^2 + b^2 = c^2 について (a,b,c) = (m^2-n^2, 2mn, m^2+n^2) とおく(計算したらこのようにおいても成り立つことが分かります)。
このm,nは、数式a_i
a_i = 2*a_(i-1) + a_(i-2), a_1 = 1, a_2 = 2
の第k項、第k-1項にあたる。
こうなると、隣り合ったピタゴラス数が求められるらしいです。さて、これを証明してみましょう。
a^2 + b^2 = c^2 について (a,b,c) = (m^2-n^2, 2mn, m^2+n^2) とおく
はいまずここ。当てはめてみると、
(m^2-n^2)^2 + (2mn)^2 = (m^2+n^2)^2
となります。Aの式に当てはめてみると、
m^2-n^2 - 2mn = 1 もしくは m^2-n^2 - 2mn = -1 となればいいということです。よって、m^2-n^2 - 2mn = ±1 (式(r))であることを証明していきます。
次に、
このm,nは、数式a_i
a_i = 2*a_(i-1) + a_(i-2), a_1 = 1, a_2 = 2
の第k項、第k-1項にあたる。
より、m = a_k, n = a_(k-1) とおいて式(r)に当てはめると
(命題) 数列a_i = 2*a_(i-1) + a_(i-2), a_1 = 1, a_2 = 2 は整数k(k>1)において(a_k)^2 - (a_(k-1))^2 - 2*a_k*a_(k-1) = ±1 が成り立つ
として証明を進めていきます。
では左辺を展開していきます。
(4*a_(k-1)^2-3*a_(k-2)^2-a_(k-3)^2+4*a_(k-1)*a_(k-2)-4*a_(k-2)*a_(k-3)) - (4*a_(k-2)^2+8*a_(k-1)*a_(k-2)+4*a_(k-1)*a_(k-3)+2*a_(k-2)*a_(k-3))
= 4*a_(k-1)^2-7*a_(k-2)^2-a_(k-3)^2-4*a_(k-1)*a_(k-2)-4*a_(k-1)*a_(k-3)-6*a_(k-2)*a_(k-3)
ここで定義より、a_(k-1) = 2*a_(k-2)+a_(k-3)であるので代入する。
=4*(2*a_(k-2)+a_(k-3))^2-7*a_(k-2)^2-a_(k-3)^2-4*(2*a_(k-2)+a_(k-3))*a_(k-2)-4*(2*a_(k-2)+a_(k-3))*a_(k-3)-6*a_(k-2)*a_(k-3)
=(16-7-8)*a_(k-2)^2 + (16-4-8-6)*a_(k-2)*a_(k-3) + (4-1-4)*a_(k-3)^2
=a_(k-2)^2 - 2*a_(k-2)*a_(k-3) - a_(k-3)^2
=a_(k-2)^2 - a_(k-3)*(2*a_(k-2)+a_(k-3))
=a_(k-2)^2 - a_(k-1)*a_(k-3) ・・・ 式(Ⅰ)
となりました。ここで、式(Ⅰ)をa_(k-3),a_(k-4)の式に変形する。
a_(k-2) = 2*a_(k-3)+a_(k-4)
a_(k-1) = 2*a_(k-2)+a_(k-3) = 2*(2*a_(k-3)+a_(k-3)) + a_(k-3) = 5*a_(k-2) + 2*a_(k-3)
これらを代入すると
式(Ⅰ)
= (2*a_(k-3)+a_(k-4))^2 - (5*a_(k-3) + 2*a_(k-4))*a_(k-3)
= 4*a_(k-3) + 4*a_(k-3)*a_(k-4) + a_(k-4)^2 - 5*a_(k-3)^2 - 2*a_(k-3)*a_(k-4)
= -a_(k-3)^2 + 2*a_(k-3)*a_(k-4) + a_(k-4)^2
= -a_(k-3)^2 + a_(k-2)*a_(k-4) ・・・式(Ⅱ)
を得る。同様にa_(k-4),a_(k-5)の式に変形すると、(中略)
式(Ⅱ) = a_(k-4)^2 - a_(k-3)*a_(k-5) ・・・ 式(Ⅲ) (a_(k-3)もあるじゃん！というクレームは受け付けません)
となります。この変形を繰り返すと、
(左辺) = a_2^2 - a_3*a_1 ・・・式(1)
もしくは
(左辺) = -a_2^2 + a_3*a_1 ・・・式(2)
となります。ここで、定義よりa_1 = 1, a_2 = 2です。
a_3 = 2*a_2 + a_1 = 2*2 + 1 = 5
を代入すると、
(1) = -2*2 + 5*1 = -4 + 5 = 1
(2) = 2*2 - 5*1 = 4 - 5 = 1
となり、命題は真であると証明されました。
この証明が書きたかった…！！
証明が長くなりましたが、数列a_iの第k,k-1項をm,nにすることでAは満たされます。その際に、kの数を2からインクリメントしてC,Eを満たすu,vを得るまでwhile文をゴリゴリ回していきます。
u1,u2はどちらかがuとなりもう片方がu+1に該当します。
これで、u,vの組1つを得られました。さて次はx,yを求めていきましょう。
B : 3x^2 + 3x + 1 - y^2 = 0
D : yは素数
F : xは2進数表記で600桁
先と同様、Bを満たすx,yを何個も求めていき、D,Fを満たすかをチェックします。
Bの式を変形させてPell方程式を完成させます。なぜPell方程式かは分かりません(笑) でもこれでできるんです。思いついた人すごいなぁ。
ペル方程式に関する基本的な性質まとめ | 高校数学の美しい物語
Pell方程式とは整数a,bに対し、a^2-d*b^2 = 1となる方程式です。求め方は、解の中でa+√d*bを最小にするa_1,b_1を自力で見つけ(簡単に見つかるやつならいいのかな)、以下の式で他の解a_i,b_iを求めます。
a_n + √d*b_n = (a_1+√d*b_1)^n
= (a_1+√d*b_1)^(n-1) * (a_1+√d*b_1) = (a_(n-1)+√d*b_(n-1)) * (a_1+√d*b_1) ※これはプログラム内で利用します。
ではこの形にBの式を変形させましょう。
3x^2 + 3x + 1 - y^2 = 0
(両辺を-4倍)
-12x^2 - 12x - 4 + 4y^2 = 0
-12x^2 - 12x - 3 + 4y^2 = 1
(2y)^2 - 3*(2x+1)^2 = 1
a = 2y, b = 2x+1, d = 3としたPell方程式を解けばいいのです。a,bを求めた時に、aは偶数およびbは奇数であることに注意しましょう。あとは先程のa_n,b_nを求める漸化式を利用して
とプログラムを書いてx,yが求まりました。あとは、問題ファイルのu,v,x,yにこれらを代入し
FLAGを手に入れました！
今回はCTFの問題1つと、隣り合ったピタゴラス数の証明をやってみました。こういうのもやっているんだぞと言いたかっただけです(笑)
それでは！
See you next time!
