詳解セキュリティコンテスト輪読会資料#14

範囲: p.294 - p.304

好きな問題: TSGCTF2019 OMEGA の解説と中国剰余定理

僕は当時解けませんでした。問題repository

problem.rb

require_relative 'params'

def to_complex(x)
  a, b = x
  w = Math::E ** Complex(0, Math::PI*2.0/3.0)
  a + b*w
end

def sub(x, y)
  a, b = x
  c, d = y
  [a-c, b-d]
end

def mul(x, y)
  a, b = x
  c, d = y
  [a*c - b*d, a*d + b*c - b*d]
end

def div(x, y)
  xc, yc = to_complex(x), to_complex(y)
  a, b = (xc / yc).rect
  [(a + b/Math.sqrt(3)).round, (b*2.0/Math.sqrt(3)).round]
end

def mod(x, y)
  # many times...
  100.times do
    k = div(x, y)
    x = sub(x, mul(k, y))
  end
  x
end

def norm(x)
  a, b = x
  a*a + b*b - a*b
end

flag = "TSGCTF{XXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXX}"
msg  = [flag[0,flag.size/2], flag[flag.size/2,flag.size]].map {|text| text.unpack("H*")[0].hex}
modulos = MODULOS

res = modulos.map do |m|
  [mod(msg, m), m]
end

puts 'MODULOS = %p' % [modulos]
puts 'PROBLEM = %p' % [res]

params.rb

MODULOS = [[404287, 873970], [636327, 576420], [338156, 891120], [492879, 529526], [713147, 662709], [993025, 655962], [175379, 419045], [563351, 899507], [542103, 840562], [166864, 951865], [838219, 258645], [480223, 854215], [501143, 184397], [772065, 140479], [236644, 810087], [161194, 189147], [16555, 527922], [310980, 636755], [253315, 757357], [766680, 848857]]
PROBLEM = [[[27524, 160977], [404287, 873970]], [[325486, 117503], [636327, 576420]], [[-299791, -375867], [338156, 891120]], [[-129656, -190359], [492879, 529526]], [[203809, -36629], [713147, 662709]], [[-774345, -129438], [993025, 655962]], [[-34825, 113838], [175379, 419045]], [[36654, 244380], [563351, 899507]], [[242760, -28048], [542103, 840562]], [[104230, 294180], [166864, 951865]], [[49817, -208346], [838219, 258645]], [[14923, 288894], [480223, 854215]], [[100017, 96567], [501143, 184397]], [[172757, 22647], [772065, 140479]], [[74229, 261518], [236644, 810087]], [[-27715, -76038], [161194, 189147]], [[116245, -82633], [16555, 527922]], [[368302, 365778], [310980, 636755]], [[43295, -101755], [253315, 757357]], [[238152, 235140], [766680, 848857]]]

問題を紹介したい理由: 中国剰余定理は、詳解セキュリティコンテストでは「整数とその剰余」に関するものとして紹介されていた。実際は一般に(単位元を持つ)環とそのイデアルに拡張できる。TSGCTF2019 OMEGAはその環としてアイゼンシュタイン整数環を用いていて、中国剰余定理の数学的背景を知る上で面白いかなと思って持ってきました。

問題概要: $x = a+b\cdot \omega$ , ただし $a,b\in\mathbb\{Z\}, \omega = e^\{i\cdot \frac\{2\}\{3\}\pi\}$ なる $x$ を扱う。引き算(sub)、掛け算(mul)、割り算(div)と、絶対値(norm)が与えられている。MODULOSという複数の値に対してmod演算として定義されている関数があり、このmod関数の出力から元のmsgを復元することが目標になる。

解法: このような $x$ を集めたものはアイゼンシュタイン整数環になる。この環での演算が四則演算に対応している。足し算を書く(add) 続いて、(TODO)

TODO: mod演算が妥当なことを示し、道具として使う関数たちの妥当性確認してからCRTに持ち込む

参考リンク

離散対数問題に対するアプローチ

TODO: BSGS, pollard-pho

RSAの動画

これ雰囲気動画として一番最初に見るとわかりやすいサマーウォーズの暗号、ガチで解けるかやってみた【RSA暗号】 - QuizKnock

安全性

RSA暗号の安全性での「 $c=m^e\pmod N$ から $m$ を求めるのは難しい」はRSA仮定と呼ばれる。このような〇〇仮定というのは暗号分野でよく使われる。ペアリングなど複雑な道具を使う分野だと仮定が増える。一般には仮定はよく使われていてシンプルなものであるほど受け入れられやすいらしい。