ぺんぎんさんのおうち

日本語勉強中のドイツ産ペンギンがいろんなことを書く

InterKOSENCTF (2019) strengthened 供養

Write-upを堂々と公開できるほどのスコアでもないため, 供養としてあげておく.

問題の概要

問題のソースコードからまずは以下が読み取れる.

  • nが2048 [bits]
  • eが3
  • c := pow(flag, e, n)
  • flagはKOSENCTFから始まる

eが3とかなり小さいので, cの3乗根を取れば終わりかと思いきや,

while pow(m, e) < n:
    m = m << 1

によって me > n とされるため3乗根をとっても意味がない.
が, 左シフト演算が右に0をパディングしているだけと考えるとmは以下のように表せる.

m = flag || {0}^k

つまり 平文の下位ビットのほとんどが0 である.
これだけわかればなんとインターネットの海を漂うことで解けてしまう.

RSA 平文のほとんどのビットがわかっている」 のようなクエリで検索すれば出てくるだろう.

おしまい.

解法

おしまい. ではない.
ここからはCoppersmith's Theoremについて軽く触れ, 実際のsolverについて解説する.


Coppersmith's Theorem

モニック多項式1 f(x)において, 根が剰余Nのd乗根以下であれば高速に求めることができる. dは多項式の次数.

つまり $$ f_{N}(x_{0}) = 0 $$

上式を満たす \(\boldsymbol{x_0}\)を効率的に求められる.

今回の問題においては flag < n^(1/3) を満たしているという前提で解くことになる.


問題における多項式

まずは問題を安直に解けなくしている諸悪の根源を確認する.

m := m << 1

1ビットの左シフトが2倍演算であることを考えると, kビット左シフトは

m := m << k 
-> m = m * 2^k

と一般化できる.

暗号化の部分を詳しく表記すると

\begin{eqnarray} m^{e} & \equiv & c \, mod \, N \newline {(flag*2^{k})}^{e} & \equiv & c \, mod \, N \end{eqnarray}

これを書き換えると

\begin{eqnarray} {(flag*2^{k})}^{e} + t*N & = & c \newline {(flag*2^{k})}^{e} - c & = & 0 \end{eqnarray}

t = 0としてNを消している. これについてはちゃんと意味があるのだが, ここでは省略する.

以上より, 解くべき多項式は次のようになる.

$$ f_{N}(x) = (x * 2^{k})^{e} - c $$

あとはこれをsage神に投げると解いてくれる. ただしkは不明なのでここだけ全探索. 暗号化する前のmは約700bitsになるはずなので, それを考慮するといいかもしれない.


solver

n = 略
c = 略
e = 3

beta = 1
for k in range(2, 500):
    PR.<x> = PolynomialRing(Zmod(n))
    f = (2^k * x)^e - c
    f = f.monic()

    xs = f.small_roots(X=2^450, beta=beta)
    for x in xs:
        m = 2^k * x
        if pow(m, e, n) == c:
            print 'k =', k
            print 'm =', hex(int(m))
            print 'x =', hex(int(x))
            print

まとめ

暗号って面白いですね.

ykm_crypto/easy/p1 にこの問題を少し改良したものを公開している. 興味があれば解いてみて欲しい.



1: 最高次数の係数が1の多項式

近況

ykm11.hatenablog.com

 

2019年初の投稿. 3月の学会の予稿論文を提出しました. お疲れ私. 

あとは今月講義受けて来月試験受けて卒論書けば終わりっぽいです. 

 

 

DARK SOULS REMASTERED [Switch版] 

先月末に購入して, 休みが明けるまでずっとやってました. 現在進行形でひたすらやってます.

最初に作ったデータは2週目突入して, ジークマイヤーとソラール生存ルートやって終了ました. 今は新しいデータでニト剣無双してます. 全ボス撃破とかもやりたいですが, NPC敵対はしたくないのでプリシラやグウィネヴィアは戦いたくない感あります.

いやぁダークソウルは面白いですね. 

 

プレイしてて気づいた点を上げていきます. 主にフリーズ関係.

実際にフリーズしたところ

・不死教区教会の, 祭祀場行きのエレベーター上の階段で上R2(ジャンプ攻撃)入力

・混沌の苗床を倒したあと, カメラを入り口側に向ける

 

描画がぐらついたところ

・不死教区教会の2階で亡者が大量に画面に写り込んだ

・エレーミアス絵画世界の結ばれた亡者が画面に写り込んだ

 

 

(描画)処理が重くなるときにぐらついたりフリーズしたりする(プレイヤーはどうすることもできない)ので, ここで魔術とか使うと確実に止まりそうです. クラーグ戦で溶岩まみれになってもぐらつくことはなかったので炎が原因とはなりえないかもしれませんが.

Switchは結構な処理性能あったはずなんですがダークソウルはあまり向かないんですかね. 

 

 

そういえばフラムトはグウィンの盟友で, 始まりの火を継ぐ者を探してるから巡礼者(主人公)に王のソウルを集め火を継いでくれって頼んでたのに, グウィン倒したあと闇の王エンドで「我カアス, フラムト あなたに仕えます」みたいなこと言ってるのなんだろう. カアスは火の時代を終わらせたくて, 逆にフラムトは火の時代を終わらせたくないはずなのにどうして闇の王として君臨することを赦しているのか. 

フラムトの目的はなんだろうね. 放っておいてもいつかは始まりの火は消えるので火の時代の終わりを願うなら継いでくれなんて言わないはず. 闇の王エンドでカアスだけが出てくるなら納得できるけど, そこにフラムトがいちゃダメだろぉ.

おLんLんLんどはじまるよ.ykm

これは 高専 Advent Calendar 2018 24日目の記事です. ところで来週は僕の誕生日です.

なにを書こう

来週は僕の誕生日なんですが実を言うと, こんなの書いてないで学会論文を書かないといけないんですよ.
でも登録したからには意地でも何か書いてやろうと, しかしネタがありません.

脳裏に浮かんだものを以下に挙げます.

  • 趣味
  • 高専の話
    • 5 + 1 年過ごした所感
      -> 人間が通えるところじゃない(立地と寮をどうにかしてくれ)
    • 留学
      -> 個人的に聞いてくれ
    • 今年したこと
      -> 生きた
    • 編入
      -> 学力を持ち合わせていないため書けない


タイトルにもあるように, "LLL Lattice Basis Reduction Algorithm" について書きます.
趣味の暗号と大学編入で勉強するであろう線形代数の話の融合ということで.

ただしここで書く内容はあくまで僕が理解したものなので正しいという保証はできません. 論文を読むなどしてください.


LLL Lattice Basis Reduction Algorithm

直訳すると LLL格子基底削減アルゴリズム です(以降LLLと略記).

LLLは格子の基底を小さいものに変換するアルゴリズム(直訳まま)で, これ自体は暗号ではありませんがLLLを応用して暗号の解読等に使用されます. Coppersmith's attackやBohne-Durfee attackが有名ですね.


Lattice

Lattice(格子)は基底ベクトル B = {b1, b2, ...} の線型結合によって表すことができるベクトルの集合です.

L := {Σxb : x ∈ Z, b ∈ B}

たとえば基底ベクトル b1 = (1, 0), b2 = (0, 1) の線型結合 s*b1 + t*b2 は格子です.

ここで重要なのは, 同じ格子を張る基底ベクトルの組み合わせは1つだけではないということです.
例として, B1 = { (1, 0), (0, 1) } と B2 = { (2, 1), (1, 1) } は同じ格子を張ります.

以下に格子の例を示します.

f:id:ushiromiya3:20181201194849j:plain

f:id:ushiromiya3:20181201194902j:plain

赤と青で示された基底ベクトルが同じ格子を張っています. まさか!と思う人は確認してみてください.

今考えている格子の基底ベクトルを, 同じ格子を張り且つ小さなものへ変換をLattice (Basis) Redcution と言い, LLLはその一種となります.
上の図で言うと, 青の基底ベクトルが与えられて赤の基底ベクトルを導出するような感じです.


線形独立

一次独立ともいい, 線形結合でそれぞれに0を掛けた場合にのみ0ベクトルを作ることができるとき線形独立であるといいます.

ベクトルb1, b2の線形結合で  
s*b1 + t*b2 = 0  
となるs,  tが0だけのときb1, b2は一次独立である

s, tが0以外で0ベクトルが作れたら線形独立ではないということです.
たとえば

3*b1 - 2*b2 = 0 
3*b1 = 2*b2
3/2 * b1 = b2

b1の定数倍によってb2が得られることがわかります. というわけで基底にはなり得ないわけです. 線型独立かどうかは基本変形行列式求めて確認しますよね.


LLL process

projectionという関数を定義します.

proj(u, v) := <u, v> / <u, u> * u ; <x, y> is dot-product with x and y

あとはGram-schmidtの直交化を応用していけばいいです. はい. Lenstra–Lenstra–Lovász lattice basis reduction algorithm - Wikipedia

基底が削減されているとする条件を満たしているか, とか満たしていなければswapしてまた直交化...みたいな感じでやっていきます.

全部マルチとスマブラが悪いので.. ちゃんと解説できなくてすまんという顔をしています.


最後に

時間が取れなくなりました. 悲しいね.

鋼の錬金術師 FULLMETAL ALCHEMIST(AmazonPrimeVideo)
54話の終わり方が好きです. EDの入り方がかっこよすぎる. 見てください.


Bibliography


あわせて読みたい


Mein Geburtstag ist bald

Für mich kaufen etwas bitte 翻訳使うな
Wunschzettel

近況

ykm11.hatenablog.com

 

無事に家も決まり, あとは学会論文と卒論書いて卒業するだけ. 

 

 

 

怖い

弟とスマブラをやっていた土曜日の夕方, スマホの通知が目に入る.

中学卒業以来なので5,6年は会っていない. 宗教勧誘ではないか?とツイのおたくたちに言われたが違うと信じたい. 

 

この時の僕の気持ち

f:id:ushiromiya3:20181213131826j:plain

 

断る理由も特になかったのでひとまず会うことにした. 詳細は追って連絡するとのこと.

 

そして.. 

茶店で集合となると本当に宗教勧誘っぽくなる. マックでいいじゃん. 

 

しかしメンバー的にも関係性が全く見えてこない. どうして僕が呼ばれたのか本当にわからない. 

 

茶店に着いたときの僕の気持ち

f:id:ushiromiya3:20181213131923j:plain

 

 

結局なんの話だったのか

ビットコインを利用した, いわゆるマルチ商法.

最初にビットコイン(ブロックチェーン)の話があったので,  「(ブロックチェーンは)論文読んだから知ってますよ」と言ったら驚かれた. 

 

クラウドマイニングをやっている企業に1口nドル投資すると配当が貰えますよ〜というもので, 新しく投資してくれる人を紹介すると紹介料としてさらに配当が...という典型的なやつ. 

 

話を聞く分にはまぁ筋は通ってるのかなといった印象だったが, ここでは割愛するがいくつか疑問点もあったし普通に「金無いからしない」で断った. . 

 

とりあえずHDDに移しておくことにした.

全体的に前置きが長く, 途中から「早く家帰って弟とスマブラしてぇ...」とか考えてた.

 

 

何人かこの投資に乗っている友人(?)がいるらしく, その友人の大学で「今そういった勧誘が流行してるらしいから〜」みたいな注意喚起があったらしい. 

 

 

マルチ商法って意外と身近なものなんだなとおもいましたまる

 

 

 

 

ところで家帰ったらNEW GAME!届いてた

紅葉ちゃん...すこなのだ...

ひふみんはもっとすこなのだよ....毎日抱いて寝てる.

 

如何にして家を探すか

UEC Advent Calendar 2018 - Adventar 9日目の記事になります.  

 

はじめに, WHO AM I

趣味で女子高生をやっている高専のお兄さんです.  次の4月から3年次編入予定なのでまだUEC生ではありませんが, @Knuim_さんに声を掛けていただき筆をとりました. 今回はUECへ進学する人が通るであろう 部屋探し(実家通いの方が多いかもしれない) について書きたいと思います. 今後の参考になれば幸いです.

本記事は都外から, 特に関東圏以外からの学生向けになると思います(筆者が四国からの進学なので).

 

自分で読み返してもあまり参考にならなさそうなので最後のまとめまで読み飛ばしてください.

 

下調べ「部屋探しなんもわからん」

地方からの交通費や何日か滞在することを考えるとなかなか東京へ行けないですよね. 

結局見つからなかった..というのは非常に辛いです.  

 

筆者は通学時間を利用してよく物件を眺めていました. [

【SUUMO】関東の不動産情報・不動産売買・住宅情報]

あ❗️ スーモ❗️🌚ダン💥ダン💥ダン💥シャーン🎶スモ🌝スモ🌚スモ🌝スモ🌚スモ🌝スモ🌚ス〜〜〜モ⤴スモ🌚スモ🌝スモ🌚スモ🌝スモ🌚スモ🌝ス~~~モ⤵🌞

SUUMOで物件を眺めても, 結局は東京に行かないと契約はできません.

が, どんな物件があるのかや値段/相場だけでも見ておくとよいと思います.

家賃の上限/下限や駅から徒歩どれくらいかの指定が可能なので自分の好みに合わせて検索しましょう. 

たとえば筆者は

最寄り駅 : 西調布

駅から徒歩 : 10分以内

家賃 : 5.0万円 ~ 5.5万円

こんな感じで調べました.  

 

家賃は安いに越したことはありませんが安すぎると逆に不安になることがあるので, "家賃 = 質" だと思って筆者は5.0万円以上にしています.

稀に4万円台で条件の良い物件があるので4.5まで下げてもいいかもしれません.

 

 

いくつか気に入った物件が見つかれば, その物件を紹介している不動産屋をメモしておきましょう. 他にも良さそうな物件を紹介してくれる可能性があります.

 

「多すぎる💢💢💢💢💢」

 

ということで調布駅周辺の不動産屋をいくつかメモしておいて, 現地着いてから順番に見ていくことにしました.

 

 

いざ東京へ

決戦は12月9日, 今日ですね.

実は「家探しをしました〜」ではなく「今まさに家を探してます〜」という記事になっています.

 

夜行バスで朝6時前に新宿に着きそのまま友人の家で休憩し, 家を出たのは15時頃でした(調布に着いたのが16時前). 

東京で泊めてくれる知り合いがいるのはレアケースかもしれませんが, 滞在費を抑えることができるので利用できるのであれば利用しましょう. 筆者も友人には入試のときなど何度かお世話になっています. 

 

さて調布駅に着いてからですが, さっそく不動産屋に向かいました. 調布駅の近くには不動産屋がいくつもあるので, 部屋の条件が定まっているのであれば適当に立ち寄ってもいいかもしれませんね. 

 

4月からの入学で2,3月から入居可能である部屋を探している旨を伝えると家賃の支払いを2月まで待ってくれる物件を紹介してくれました. 他にも条件があればそれを考慮して紹介してくれるのでなんでも伝えておくと良いと思います. 

 

 

結果発表

無事に決まったので4月から友人の家で居候する必要がなくなりました. 

 

契約手続きしていると筆者が決めた物件への問い合わせがあり, あと少し遅ければ借りられていたそうです. 早めに行動しましょう..

 

 

まとめ

 

  • とりあえず条件を決めておく(洗濯機が屋内/屋外, バストイレ別など)
  • 不動産屋をいくつかマッピングしておく
  • ギリギリになると他の人に借りられてしまうので早く動く

 

 

 

おまけ 

家探すだけだと味気ないので僕の.vimrc(or neovimならinit.vim)の紹介もしたいと思います. (3,4年くらいvimを使っているがまだ本領発揮できていない)

 

set number
syntax on
set tabstop=4

set t_Co=256
autocmd ColorScheme * highlight Visual ctermfg=14 guifg=#000000
autocmd ColorScheme * highlight String ctermfg=84 guifg=#000000
autocmd ColorScheme * highlight Comment ctermfg=227 guifg=#000000

colorscheme molokai

noremap j gj
noremap k gk

set shiftwidth=4
set expandtab
set showmatch
set nowritebackup
set nobackup
set noswapfile
"set textwidth=0
set colorcolumn=80

 

let g:tex_conceal=''

let g:go_fmt_command = "goimports"

 

nnoremap <silent><C-e> :NERDTreeToggle<CR>
let g:deoplete#enable_at_startup = 1
let g:rainbow_active = 1

 

"dein Scripts-----------------------------

略..

 

カラースキーマにmolokaiを使っていて, 一部色を変更しています. 

 

 

最初の二行

set number

syntax on

これだけでも十分戦えると思いますが, vimに慣れてきてイケイケな設定を書きたくなったらどんどん追加していきましょう!!

次にdeinで管理しているプラグインです.

 

luochen1990/rainbow

括弧 ( [ { } ] ) が対応する位置で光ります.

 

Yggdroot/indentLine

インデントをわかりやすくしてくれます,

 

scrooloose/nerdtree

左からウニョっとエクスプローラが出てきます.

もはやIDEですよクォレハ.

 

Shougo/deoplete.nvim

構文や変数の保管ができるようになります.

もうIDEじゃないですかこれ?

 

 

これらを設定して(neo)vimを開くと下の画像のようになります.

 

f:id:ushiromiya3:20181207142507p:plain

 コメントや""で囲んだ部分, 括弧のハイライト, インデントがある部分には線が入っています. 

 

あとはsageを書くときのために.sageをpythonスクリプトとして認識させたりしてます.

autocmd BufRead,BufNewFile *.sage set filetype=python

 最近VimLatexを書くとき(特に数式)に, Conceal機能によってΣとかΠとかをコンソール上で変換してくれちゃってるのでキャンセルします.

let g:tex_conceal=''

 

 

こんな感じでしょうか. 

UECではEmacsを使った講義があると聞いていますがVim使いの俺たちは..

 

よいVimライフを!!

 

 

余談

3年次編入でも歳はB4相当なので入学式が辛い.