ブログ移住します
移住先 -> https://project-euphoria.netlify.app/
表題の通りです。ブログ名は相変わらず"Project Euphoria"です。
新ブログはZolaという静的サイトジェネレータを使ってNetlifyでホストしてます。移行する理由は次の通りです。
移住理由
1番大きいのは文書投稿プラットフォーム全体への不信感です。はてブロはかなりまともだとは思いますが、Qiitaの興味タグ強制開示事件やnoteのIP流出事件(とその後の悪い対応)等を見ていると"文章投稿"をプラットフォームに依存させるよりは"ホスティング"だけをあるサービスに依存させた方が良いと考えるようになりました。
次に大きいのはカスタマイズ性です。Markdownを食わせるとテーマに沿って良い感じにページを生成してくれるZolaですが、テーマを改造すれば自分の好きな見栄えにすることが出来ます。ZolaはTeraというテンプレートエンジンを採用しており、ページの構造はこちらで自由に弄ることが出来ますし、見た目を直接弄りたかったらCSSを弄ればなんとかなります(もっとも私の性格的に後者はあまり弄らないと思う)。
3つ目はローカルで完結する部分が増えることです。例のnoteの騒動の際に過去に書いていた記事を保存しようと思ったのですがエクスポートが出来ず(この不自由さは以前から不満だった)結局アカウントごと爆破しました。一方これからは手元で書いたMarkdownを食わせる形なので記事の本体は手元に残ります。なお、はてブロに上げた一部の記事も移植する予定ですが、こちらはエクスポートは出来ないものの殆どをMarkdownで書いているのでコピペとちょっとした手直しで済みそうです。
4つ目は書きやすさです。はてブロだと数式を書く際に上付き/下付き文字がはてな記法の方と被るらしく、エスケープする必要がありました。これで多々引っ掛かっている上に直すのも面倒なのでかなり不便な仕様です(もし解決策があったら私の検索不足です、ごめんなさい)。それ以外にもわざわざ[tex: ~]
のような独特の書き方をしなくてはならないのが気に入りませんでした。
今後
HackMDを本格的に使うようになってから殆どの文章をあちらに書いており、ここの存在意義が無くなっていました。技術系とそうでない文章(先日のエロゲ感想みたいな)で分けても良かったのですが、後者のような文章を書く気が最近全く起きないのと、投稿先が複数あると使い分けるのが面倒になるというような理由からこちらは多分一生更新しません。
去年分のWriteup記事はおそらく新ブログの方に移植しますが、それ以外のSteamや性癖に関する記事、CTF関連ポエムは機を見て消します(自分で読み返したい記事があるのでローカルにコピペして残しておく)。というのも更新しないプラットフォームを放置しているのが個人的に嫌だからです。
ブログ自体ははてブロで購読しているブログの更新を受け取りたいので多分残っていますが、最終的にはこの移住告知記事を残すだけだと思います。リンク切れや検索結果で存在しないページが出てくるのもアレなのでもしかしたらWriteupぐらいは残っているかもしれません。
結び
PCゲームのことだけ書いてた時期から起算して2年半、Twitterの知り合いしか見ていなかったであろう本ブログもCTF等のパソコンカタカタ活動を通して色々な人が見てくださったみたいで筆者冥利に尽きます。
これまでありがとうございました、引き続き移住先の方もたまに見てくださると幸いです。
Pwn2Win CTF 2020: Omni Cryptoの復習
はじめに
もう1週間以上前になりますが、Pwn2Win CTF 2020に出ていました。当日は自明なブロック暗号問題を1つ通して残りの時間をRSA問題に費やして解けずに終わりましたが、昨日復習をようやく終えたので解けなかったRSA問題の復習Writeupを生成してこちらに上げようと思います。遅れたのはサボっていたとかでは無くHSCTFとかDefenit CTFに出ていたからです...嘘です、面倒くささと後回し癖が発動しました。
ところで宣伝ですが、このCTFからWriteupをチームのリポジトリにpushするようにしたので良ければそっちも覗いてみてください↓。Pwn2Winの分は日本語で書いていますが、以降に出たCTFの一部の問題はグローバル志向なので英語で書いています。
Omni Cryptoの問題概要
通常のRSA問題のように公開鍵と暗号文が与えられます。指数は例によって65537で特に異常は見られません。の生成用のコードが与えられ次のようになっています。
def getPrimes(size): # [16, 504] half = random.randint(16, size // 2 - 8) # [8, 503] rand = random.randint(8, half - 1) # [17, 1000] sizes = [rand, half, size - half - rand] while True: p, q = 0, 0 for s in sizes: p <<= s q <<= s chunk = random.getrandbits(s) p += chunk if s == sizes[1]: chunk = random.getrandbits(s) q += chunk p |= 2**(size - 1) | 2**(size - 2) | 1 q |= 2**(size - 1) | 2**(size - 2) | 1 if gmpy2.is_prime(p) and gmpy2.is_prime(q): return p, q
コード中ではsize=1024
として2つの素数を生成しその積を公開鍵としています。
ここからに関して次のような関係があることがわかります。
ここではがsize - half - rand
に、がhalf
に対応します。
Writeup
今回使うのは鍵の一部が判明している際のCopperamith's Attackです。SageMathのsmall_roots()
は引数beta
を適当に指定することで与えられた合同方程式を法の約数の下で解くことが出来ます。一般的なRSA問題ではと2つの素因数に分解できるのでの下での解を求める事が出来ます。したがってのような方程式をを知らない状態でも解くことが出来、この解との和によってを求めることが出来ます。なお、この攻撃が成功するのはの半分+α以上がわかっている場合だそうです。例によってももいろテクノロジーさんの記事を貼っておきますので詳しくはそちらを参照してください。
ではこのをどうやって求めるかですが、実際にを先程のから計算し、bit数を考慮するとの下位bitはのそれと一致し、上位bit(なお、これはrand
に一致する)はのそれと一致することがわかることから求まります。
前者を求める方法ですがという方程式が成り立つことからSageMathのnth_root()
を使って求めることが出来ます。詳細は公式Docsを読んでください↓
後者に関しては単にの平方根を取って上位rand
bit分を得るだけで済みます。
ここで問題になるのはrand
とhalf
がいくつになるのかです。どちらもわかっていれば共通部分が上位下位でそれぞれ幾つであるかも判明するので前述の手法で簡単に解けることが期待できます。また、片方しかわかっていなくても1024bitの内、残りのbitを全探索することで解けることが期待できます。しかし今回はどちらもわかっていません。そこでrand
とhalf
で2重ループを回すということが考えられます。
おそらくそれでも何時間か回せば解けるのですが(たぶん)、当日は計算量を気にしてその方針は却下しました。ここで再びget_primes()
関数を見るとhalf
が最大でも504bitであることがわかります。したがって共通部分は上位下位合わせて1024 - 504 = 520bitは確実に確保されていることがわかります。そこでhalf
に対応するbit数であるを504に固定し、残りの520bitの内幾つが上位で幾つが下位であるかを総当りします。この方針ですと正しいhalf
は求まりませんが、のhalf
の部分に対応する値が求まってしまえば、その内の上位と下位はそれぞれ共通部分の一部であることが期待できます。図に示すと下記のようになります。
|--- common ---|--- unknown (fixed: 504 bit) ---|--- common ---|: 立てた方程式 |--- common ---|--- root ---|--- common ---|: 解いた後、rootが解 |--- common ---|(--- common of root ---|--- root ---|--- common of root---)|--- common ---|: 解を上下共通部分と未知だった部分に分解
これを動かすとrand
、つまり上位の共通部分が150bitを過ぎたあたりぐらいで解が求まりました。後はRSAの復号手順にを放り込んで終わりです。
Code
SageMathを使用して解きました。
N = 0xf7e6ddd1f49d9f875904d1280c675e0e03f4a02e2bec6ca62a2819d521441b727d313ec1b5f855e3f2a69516a3fea4e953435cbf7ac64062dd97157b6342912b7667b190fad36d54e378fede2a7a6d4cc801f1bc93159e405dd6d496bf6a11f04fdc04b842a84238cc3f677af67fa307b2b064a06d60f5a3d440c4cfffa4189e843602ba6f440a70668e071a9f18badffb11ed5cdfa6b49413cf4fa88b114f018eb0bba118f19dea2c08f4393b153bcbaf03ec86e2bab8f06e3c45acb6cd8d497062f5fdf19f73084a3a793fa20757178a546de902541dde7ff6f81de61a9e692145a793896a8726da7955dab9fc0668d3cfc55cd7a2d1d8b631f88cf5259ba1 size = 1024 top_raw = isqrt(N) bottom_dict = {} bottom_bit_range = range(17, size - 16 - 8 + 1) for bottom_bit in bottom_bit_range: bottom_dict[bottom_bit] = [] xs = mod(N & (2^bottom_bit - 1), 2^bottom_bit).nth_root(2, all=True) for x in xs: if x >= 2^(bottom_bit-1): bottom_dict[bottom_bit].append(x) unknown_bits = 504 known_bits = size - unknown_bits end = False for rand_bits in range(8, 504): print(rand_bits) rand = (top_raw >> (size - rand_bits)) << (size - rand_bits) bottom_bits = known_bits - rand_bits bottoms = bottom_dict[bottom_bits] for bottom in bottoms: PR.<x> = PolynomialRing(Zmod(N)) f = ZZ(rand) + 2^bottom_bits * x + ZZ(bottom) f = f.monic() roots = f.small_roots(X=2^unknown_bits, beta=0.3) if roots: p = ZZ(rand) + roots[0] * 2^bottom_bits + ZZ(bottom) q = ZZ(rand) + roots[1] * 2^bottom_bits + ZZ(bottom) print(p, q) if p*q == N: print("[+]: found") end = True break if end: break
Flag
CTF-BR{w3_n33d_more_resources_for_th3_0mni_pr0j3ct}
反省点
実はこの問題で使われているget_primes()
では、下位共通部分であるsize - rand - half
が512を超える確率が2/3ぐらいあり、当初はその仮定で考えていました。前述のように下位共通部分はnth_root()
で簡単に求めることが出来るのでこれをとおいてを求める問題だと思っていました。しかし、実際は下位共通部分はそこまで大きくなく、この方法だと求めることが出来ません。上位bitもの平方である程度推定できることも気付いていましたが両者を組み合わせると計算量が2重ループでひどいことになると思っていたのでそんな問題を出すわけ無いだろうと思い、下位共通部分が大きいことに固執していたのが大きな敗因の1つです。
結び
ここまで読んでいただきありがとうございました。数カ月ぶりのCTFで以前のようにCoppersmith問題を通すようなパフォーマンスが出なかったのは残念ですが楽しかったです。これを書いている現在も続けて2つのCTFをこなした後でまだモチベーションもあるのでCTF強化月間を続けていけたら嬉しいです。
次回は気が変わらなければ2020 Defenit CTFで出題されて興味を持ったので、wavのステガノグラフィーに関するアプローチと考察, 自前実装を書こうと思っています。記憶やアイデアが錆びないようにできるだけ早い投稿を目指します。
参考文献
Tonelli-Shanksのアルゴリズムについて
はじめに
前回がCTFポエムだったので今回は真面目な事書きます。
今回は平方剰余の問題を解く際に登場するTonelli-Shanksのアルゴリズムについて勉強したのでそれをまとめました。といってもアルゴリズムの解説はだいたい英語版Wikipediaを訳したのに加筆修正を加えただけなので英語が読める方は該当記事を読んだ方が早いかもしれません。
また、CTFのCrypto問題の勉強の一環でこの記事を書いているのでもしかしたら競技プログラミングをやっている方と流儀が異なるかもしれません(特に言語、ここでの実装はPythonです)、そこはご了承ください。
前提知識が多少面倒で平方剰余に関する知識として"ルジャンドル記号"と"オイラー規準"が登場します、と言っても式と意味はそこまで難しくないので適当にググる程度で問題ないと思います(実は筆者もオイラー規準や平方剰余の相互法則の証明は眺めた程度で真面目に追ったり自力でしたりしていない)
それと一番大事なお断りですが、もし誤字脱字、誤植、論理の飛躍、そもそも根本的に違う箇所がありましたらコメントかTwitter(@Xornet_Euphoria)までよろしくお願いします(DMは解放していませんのでお手数ですがリプでお願いします)
解きたい問題
今回解きたい問題は次の通りです
となる整数を求めよ、但し、は奇素数とする
簡単に言えば法の下での平方根を求めよ、ということになります。また、この問題はの値によって解の存在の有無が変わってきますがここでは解ける場合を与えられたとします(ちなみにその判定については↓のオイラー規準で紹介します)
簡単に解ける場合
ここでの値によって簡単に解ける場合があることを示します。は奇素数なので整数を用いて、の2通りに表すことが出来ます。この内、後者()の場合はフェルマーの小定理を利用することで簡単に解くことが出来ます。
フェルマーの小定理からとなります。
ここでであることからとなります。
したがってとなることからと簡単に解けます。
ただ、これをの場合に適用しようとしてもが上手く残ってくれる形にならないので使えません、そこでTonelli-Shanksのアルゴリズムが使われます。
オイラー規準
前述の通り、この形の問題には解が存在する場合と解が存在しない場合があります。例えばの場合を考え、の0以外の要素を2乗してみると1,2,4しか現れません(実際に計算してみてください)。したがって、の場合には解が存在することになり、の場合には存在しないことになります。解が存在する時ははの平方剰余であるという言い方をします。
これを次のような記号を使って表します。
- : (がの平方剰余である)
- : (がの平方剰余でない)
この記号を用いて次のオイラー規準という関係が存在します。本記事ではこれを多用します。
これの証明やなぜ計算結果がになるのかということに付いてはここでは触れません、原始根を利用した証明等があるので興味がある人は調べるか自分で証明してみてください。
また、:未満の正の整数の内、半分はの平方剰余で残りは平方剰余ではないという性質もあります。実際に先程挙げたの例でも平方剰余なものとそうでないものは3つずつになっています。
Tonelli-Shanksのアルゴリズムでは、平方剰余でない方を1つ取ってくる場面が存在します。この性質より未満の正の整数をランダムに取ってきたものが平方剰余でない可能性は1/2であるため、数のランダムな取得とオイラー規準による確認を何度も繰り返せば現実的な選択回数の中で平方剰余でないものを手に入れることができます。
アルゴリズムのお気持ち
このアルゴリズムはループを使用します、ということはやっぱり不変条件が登場し、それが満たされているようにループを繰り返しながら解を求めていく形になります。
その不変条件をいきなり提示しても意味が分からないので実際のアルゴリズムを多少追いながらこの不変条件と共に"""お気持ち"""を説明します。
まずは奇素数なのでは偶数になります、したがって別の奇数と正の整数を用いてと書くことができます。
を例にとると、となることからになります。
ではこのを用いてとなるような数を用意します。アルゴリズム中ではこの:をループ毎に変えていくことで解であるを目指すことになります。
これを両辺2乗するととなります。の2乗がとある数(ここでは)の積と合同という形になったことから対象である問題の形に近くなりました。そこでのようにを用いて表します。
仮にであった場合、となるのでがそのまま解になります。勿論最初から選んだこのようながそれを満たすことは珍しいので実際はループを繰り返しながらこのようなを目指すということになります。
そしてこのという関係がアルゴリズムで使われるループ不変条件の1つになります。この条件を満たすようにループ毎にを上手いこと選んでそれに対応するこのようなを目指します。
続いてこのように選んだが実は整数を用いて1の乗根である事を示します(指数部が普通の整数ではなく、のようにしている理由は直ぐわかります)。実はこのはになります。実際に計算してみると次のようになります。
ここではがの平方剰余である場合を扱っているため、最後の変形ではオイラー規準によってになります。
ここで2つ目の不変条件が登場します、もう既に勘の良い読者の方なら気付いているかもしれませんが(これが言いたかっただけです)、がの乗根である、になります。
1つ目の条件をループが回っても満たすにはどうすれば良いでしょうか?ループ毎に変えていくのはであるのでが定数倍された場合、はその定数の2乗倍になります。式にすると、ループによってがに、がになったとして、ある整数を用いて, であればとなりわかりやすい形にすると、であるためループの前後で条件が保存されていることがわかります。
以上の議論から1つ目の条件を満たすためには単にある係数を用意してにそれぞれ掛ければ良いことになります(には2乗したものを掛ける)。この係数を2つ目の条件を満たすように選びます。
なお、この新たなを得る段階でとなった場合は目的のが得られたことになるのでそこでアルゴリズムは終了となります。
2つ目の条件ですがとなるようながどのようになるかを考えます。はの乗根であるという条件からであれば確実にとなります。したがってループ毎にを小さくしていき、この値を目指すことにします。
またこれは完全に私のお気持ちですが、はその条件からである可能性があります。但し、の乗根であるということは乗個の選択肢があるため、がそのうちの1つである可能性はそこまで高くありません。そこでを減らしながらを更新していくことでが得られる可能性を高くしていくというお気持ちが見えます(結局を減らしていけば最終的に1になるので可能性もクソも無いと言えば無いんですが)。
アルゴリズム中ではがを満たすもっとも小さいものを探します、目的となるを一旦と置くとの範囲で見つかった場合ににを代入して値を更新します。これはの初期値であるが以下なので1から順に探っていくだけでも十分小さい計算量で出来ますが、二分探索を行うアルゴリズムがより高速らしいです(面倒なので実装は前者の1から探索する方を採用しています)。
これによってであるが、であるような整数が見つかったとします。ここで重要なのがが満たされているということです。これは次のようにの平方根を両辺でとることで示されます。
これより、もしをデクリメントした際の計算結果が1で無かった場合は-1になります。したがってとなります。
これで次のループでパラメータを更新するための、を求める準備が整いました。
ここで新たなパラメータとしてが登場します、新しく出たので初期値を使って性質を説明します。初期値はとなります、但しはの"平方剰余では無い"数です。オイラー規準のところで述べたようにこのようなは現実的な計算量で取得することが(期待)できます。そしてこのように定義されたがの乗根であることを示します(初期値なのでであることを用います)。
最後の変形はもちろんオイラー規準によるものです。実はこのがの乗根であるというのもループ不変条件の1つになります。よってループ毎に以上の3性質を満たしているを用意して、次のループでそれを更新してもそれらが満たされていれば、(数学的帰納法と同様に)同一のプロセスを更に次のループでも適用できることになります。
初期値で満たしていることを既に確認しているのは初期値でこれらを満たしていれば後はループが1つ進んでも満たされていることを示すだけでアルゴリズムの健全性が示されるからです(停止性は別で示します)。
このの2つを用いて係数をのように定義します。これによって既に3つのループ不変条件を満たしているパラメータを次のように更新します(を付けた変数が更新後の値になる)。
この更新によって1つ目の性質()が満たされていることは先程示した通りです(式を満たすように係数を掛けているので)。したがって2つ目の性質(がの乗根)と出たばかりの3つ目の性質(がの乗根)を示します。
の方から示します。を乗すると
になります。
ここでになります。また、はとなるように選んでいることからこの2つを用いてとなり、2つ目の性質はループが回っても保存されることが示されました。
同様にについても示します。を乗すると
になることから3つ目の性質もループが回った後でも保存されることが示されました。
このようにして3性質を満たすようにしながらを減らし、をへ近づけるというのがこのアルゴリズムの"""お気持ち"""だと勝手に思っています。ちなみにはループ毎に必ず減少することからループ回数に対して狭義の単調減少になります。よって必ずに到達することは示されている為このアルゴリズムが停止することも示されます。
アルゴリズム
お気持ちがある程度分かったところでアルゴリズムを提示します。といっても上記である程度書いたのでシンプルに箇条書きにする程度です、ついでに例とPythonによる実装も置いておきます。
入出力
手順
- を2で割り続け、となるようなを入手する
- の平方剰余ではない値を取ってくる
- 各変数に対し、初期値として次のように値を設定する
- 次のループを繰り返す
例
英語版Wikipedia同様の場合を例にとります。
より、になります。
の平方剰余でない数としてを取ってきます(である)。
初期値として
を設定しループを開始します。
まず、は0でも1でも無いのでとなるようなを探します。から順に探っていくとこの様な最小のはであることがわかります。
係数を得ることが出来たので次のようにを更新します。
次のループに入ります、は0でも1でも無いので再びを探すととなります。
係数を得ることが出来たので同様に値を更新します。
次のループに入ります、なのでこの時のが解の1つとなります。
当然も解になるのでも解になり最終的に求める解はの2つになります。
(実際に計算してみるととなっていることがわかる)
実装
Pythonで実装します、tonelli_shanks(5, 41)
が(28, 13)
になるはずです。
from Crypto.Util.number import isPrime def neg(x, n): return -x % n def is_quadratic_residue(a, p): if a % p == 0: return True return legendre_symbol(a, p) == 1 def legendre_symbol(a, p): if not isPrime(p) or p == 2: raise ValueError("p must be a odd prime number") return pow(a, (p-1) // 2, p) def get_q_s(p): q = p - 1 s = 0 while q % 2 == 0: q //= 2 s += 1 return (q, s) def get_nonresidue(p): ret = 2 while is_quadratic_residue(ret, p): ret += 1 return ret def tonelli_shanks(a, p): if not is_quadratic_residue(a, p): return () if a == 0: return 0 q, s = get_q_s(p) z = get_nonresidue(p) m, c, t, r = s, pow(z, q, p), pow(a, q, p), pow(a, (q+1) // 2, p) while True: if t == 1: return (r, neg(r, p)) i = m for j in range(1, m): if pow(t, pow(2, j), p) == 1: i = j break b = pow(c, pow(2, m - i - 1), p) b_pow = pow(b, 2, p) m, c, t, r = i, b_pow, t * b_pow % p, r * b % p if __name__ == '__main__': # (28, 13) # 28 ** 2 = 784 \equiv 5 \mod 41 # 13 ** 2 = 169 \equiv 5 \mod 41 print(tonelli_shanks(5, 41))
結び(筆者近況を含む)
英語版Wikipediaによればこのアルゴリズムは巡回群に一般化できるらしく、更に乗根を求めるようにも一般化出来るらしいです、凄い
今回の記事ではそこまで追いませんが純粋に興味があるのでそのうち調べてみようと思います。
今回この問題を扱ったきっかけですがCryptoHackという暗号向けの常設CTFがあり、その中の数学ジャンルの問題に平方剰余の問題があったことでした。
問題文中でTonelli-Shanksのアルゴリズムについて言及されておりそこで調べていたら、アルゴリズムが何故動くかについても気になったのでこのようなクソ長お気持ち表明文が生成されたという経緯です。
このCryptoHackですが思ったより面白く、難易度も高すぎることは無いので興味のある方は是非挑戦してみてください。記事執筆以外にもこれをきっかけに暗号用のライブラリを整備し直す等、私がCTFに復帰するきっかけにもなっています。
ところで今回のアルゴリズムは競技プログラミングでも使われているようで、調べていたらそちらでの実装例が幾つか見つかりました。CTFチームメイトの競プロ勢にも意見を募ったら過去の実装例が返ってきました。そういうわけでもしかしたらこの記事も競技プログラミング勢に捕捉されるかもしれませんが私はCTF勢ですのでもし作法や流儀が異なっていたら申し訳ないです(計算量の議論はしていない上に実装コードもC++では無くPythonであるし高速化も図っていない、試しに2048bitの素数をに設定して問題解いたら2sは確実に超えた)。 競プロ勢の皆さんもこれを機にCTFしませんか?面白いですよ。
そういえば今回この記事を書くにあたって一度HackMDにノートを作ったんですが最近HackMDの使い勝手の良さが気に入ったので技術系文書をそちらに移すことを検討しています。
具体的には編集がリアルタイムで反映される点や、同一プロジェクト間のリンクが張りやすい点が気に入りました。Scrapboxも結構好きだったんですが、Markdownが書けないのが玉に瑕なので最近は個人プロジェクトはHackMDを使っています(それに個人プロジェクトなら公開非公開設定も無料で楽にできる)。
実際にここの全技術記事を移すかどうかと今後どうするかは別にして今後もノート感覚で書いて公開できるぐらい書いたらTwitterやらに投下する方針にしようかなと思っています、その中でデカ目の記事になったら清書してはてブロに投下するかもしれません。
ちなみに今回実際に書いたノートはこちらです
以下は筆者の近況になります
3月に全くCTF関連のことをせず、4月は進路と労働で精神を破壊されたので最近はあまり元気では無かったのですが、こうやってインプットに対するアウトプットが出来るぐらいにはなったので良かったです。CTFチームも自分の進路やメンバーが皆忙しそうにしていたりであまり出れていないので次はこれを再起動出来たら良いなと思っています。
以前、何かの記事で進路を物理にしたと書きましたが、結局最後まで悩み続け、自分の人生を投じる程魅力を感じなかったことから情報系の進路を目指すことにしました、暗号理論を勉強し始めているのはそれの一環でもあります(研究したい分野が暗号理論なので)。
そういうわけで今後も暗号系の記事が増えるんじゃないかなと勝手に思っています、本当はPwnについても色々やって書きたいことがありますが一旦進路が落ち着くまでは控えめにする予定です。
ここまで読んで頂きありがとうございました。冬場にpwnしていたはずが、前述の通りCrypto熱が再燃したので次回もそんな感じの記事になるんじゃないかと思います。
最後に参考文献を載せておきますのでそちらにも目を通してみてください。
参考文献
- Tonelli–Shanks algorithm - Wikipedia: 今回の記事はだいたいここの和訳
- 整数論テクニック集(pdf): 競プロしてないけど前からちょこちょこ読んだりしてる
- mod_sqrtについて.md · GitHub
- Tonelli–Shanks algorithm - メモ: 競プロ勢のお気持ち記事、bitについて考えているのが勉強になったし面白かった