1 はじめに

チームN30Z30N総帥、Edwow Mathです。

CTF Advent Calendarの昨日（9日目）の記事は、kurenaifさんの「作問、動画作成の風景」でした。舞台裏を知る機会はなかなかないので、とても参考になります！

この記事は、CTF Advent Calendar 2022 の10日目の記事であり、また前述したkurenaifさんによるyoutube動画「【17兆通り】4bitの値20個からJavaの乱数予測をする【kurenaif】」の視聴をきっかけとした考察に関するものであります。

www.youtube.com

2. 動機

元ネタの動画は、x[i+1] := (a * x[i] + b) mod 2⁴⁸ により生成される x[i] の上位4ビットを20個集めて、乱数予測（本質的にはx[0]を求める）をするものでした。これはスゲー！実に面白い*1！と思っていろいろと考察を始めることにしました。

3. 考察（実験）

実装して動かしてみたところ、どうやら「うまくいく」場合と「うまくいかない」場合があるようでした。集める個数（Y）を増やしたり出力するビット数（X）を増やしたりすれば、「うまくいく」確率を増やせそうな感じがします。とりあえずどんな感じなのか興味が湧いてきたので、感触をつかむために（kurenaifさんがgithubで公開しているコードを参考に実装して）試してみることにしました。

具体的には、a、b、初期値（x[0]）を適当にとって、1000回試行して何回成功するか、結果を見るというものです。なお、1000回という回数に確率論的根拠はなく、単に感触をつかむための方便です。

4. 実験に使ったコード

雑然としたものですみません。

※以下の実装では、「tビットの値u個からmod(2^s)の～」となっています。

「test.sage」

import random
from Crypto.Util.number import inverse

ROUND = 1000

class LCG:
  def __init__(self, a, b, m, seed):
    self.a = a
    self.b = b
    self.m = m
    self.state = seed
  def next_state(self):
    self.state = (self.a * self.state + self.b) % self.m
  def get_bits(self, s, t):
    self.next_state()
    return self.state >> (s - t)

def choose_a(m):
  while(True):
    a = random.randint(1, m-2)
    if inverse(a, m) * a % m == 1:
      return a

def choose_b(m):
  b = random.randint(1, m-1)
  return b

for cnt in range(ROUND):
  a = choose_a(m)
  b = choose_b(m)
  seed = random.randint(1,m-1)
  lcg = LCG(a, b, m, seed)
  leaks = []
  for i in range(u):
    x = lcg.get_bits(s, t)
    leaks += [x]
  Y = vector(ZZ, [leaks[i+1] - leaks[i] for i in range(u-1)])
  ####################################################
  # Recover the seed from leaked data by using LLL:
  ####################################################
  A = matrix.identity(ZZ, u-1)
  for i in range(u-1):
    if i == 0:
      A[i,i] = m
    else:
      A[i,0] = -1 * a^i
  L = A.LLL()
  K = vector(ZZ,[round(w / m) for w in 2**(s-t) * L * Y])
  E = ~L * (m * K - 2**(s-t) * L * Y)
  X = E + 2**(s-t) * Y

  var('x')
  cands = solve_mod((a-1)*x == (int(X[0])-b), m)

  _seed = 0
  cand_seed = []
  for cand in cands:
    cand = cand[0]
    lcg = LCG(a, b, m, cand)
    check = [cand>>(s-t)]
    for i in range(u-1):
      check.append(lcg.get_bits(s,t))
    if check == leaks:
      cand_seed += [(cand - b) * inverse(a, m) % m]
      break
  if seed in cand_seed:
    success += 1
print(f"s={s}, t={t}, u={u}: {success}/{ROUND}")

5. 実験結果（生データ）

さまざまなs、t、uについて実験してみた結果です*2。

s=16, t=4, u=3: 1/1000
s=16, t=4, u=4: 53/1000
s=16, t=4, u=5: 295/1000
s=16, t=4, u=6: 641/1000
s=16, t=4, u=7: 886/1000
s=16, t=4, u=8: 942/1000
s=16, t=4, u=9: 963/1000
s=16, t=6, u=2: 2/1000
s=16, t=6, u=3: 51/1000
s=16, t=6, u=4: 646/1000
s=16, t=6, u=5: 971/1000
s=16, t=8, u=2: 1/1000
s=16, t=8, u=3: 481/1000
s=16, t=8, u=4: 988/1000
s=16, t=10, u=2: 15/1000
s=16, t=10, u=3: 967/1000
s=16, t=12, u=2: 61/1000
s=16, t=12, u=3: 999/1000
s=16, t=14, u=2: 232/1000
s=16, t=14, u=3: 1000/1000
s=16, t=16, u=2: 1000/1000
s=20, t=4, u=2: 0/1000
s=20, t=4, u=3: 0/1000
s=20, t=4, u=4: 6/1000
s=20, t=4, u=5: 41/1000
s=20, t=4, u=6: 210/1000
s=20, t=4, u=7: 545/1000
s=20, t=4, u=8: 814/1000
s=20, t=4, u=9: 924/1000
s=20, t=4, u=10: 945/1000
s=20, t=4, u=11: 963/1000
s=20, t=6, u=2: 0/1000
s=20, t=6, u=3: 4/1000
s=20, t=6, u=4: 157/1000
s=20, t=6, u=5: 797/1000
s=20, t=6, u=6: 969/1000
s=20, t=8, u=2: 0/1000
s=20, t=8, u=3: 61/1000
s=20, t=8, u=4: 890/1000
s=20, t=8, u=5: 994/1000
s=20, t=10, u=2: 0/1000
s=20, t=10, u=3: 542/1000
s=20, t=10, u=4: 996/1000
s=20, t=12, u=2: 3/1000
s=20, t=12, u=3: 969/1000
s=20, t=14, u=2: 17/1000
s=20, t=14, u=3: 999/1000
s=20, t=16, u=2: 50/1000
s=20, t=16, u=3: 1000/1000
s=20, t=18, u=2: 265/1000
s=20, t=18, u=3: 1000/1000
s=20, t=20, u=2: 1000/1000
s=24, t=4, u=2: 0/1000
s=24, t=4, u=3: 0/1000
s=24, t=4, u=4: 1/1000
s=24, t=4, u=5: 2/1000
s=24, t=4, u=6: 29/1000
s=24, t=4, u=7: 124/1000
s=24, t=4, u=8: 443/1000
s=24, t=4, u=9: 732/1000
s=24, t=4, u=10: 872/1000
s=24, t=4, u=11: 935/1000
s=24, t=4, u=12: 950/1000
s=24, t=4, u=13: 968/1000
s=24, t=6, u=2: 0/1000
s=24, t=6, u=3: 0/1000
s=24, t=6, u=4: 18/1000
s=24, t=6, u=5: 274/1000
s=24, t=6, u=6: 872/1000
s=24, t=6, u=7: 977/1000
s=24, t=8, u=2: 0/1000
s=24, t=8, u=3: 3/1000
s=24, t=8, u=4: 367/1000
s=24, t=8, u=5: 982/1000
s=24, t=10, u=2: 0/1000
s=24, t=10, u=3: 47/1000
s=24, t=10, u=4: 965/1000
s=24, t=12, u=2: 0/1000
s=24, t=12, u=3: 491/1000
s=24, t=12, u=4: 1000/1000
s=24, t=14, u=2: 0/1000
s=24, t=14, u=3: 963/1000
s=24, t=16, u=2: 5/1000
s=24, t=16, u=3: 998/1000
s=24, t=18, u=2: 14/1000
s=24, t=18, u=3: 1000/1000
s=24, t=20, u=2: 65/1000
s=24, t=20, u=3: 1000/1000
s=24, t=22, u=2: 249/1000
s=24, t=22, u=3: 1000/1000
s=24, t=24, u=2: 1000/1000
s=28, t=4, u=2: 0/1000
s=28, t=4, u=3: 0/1000
s=28, t=4, u=4: 0/1000
s=28, t=4, u=5: 0/1000
s=28, t=4, u=6: 5/1000
s=28, t=4, u=7: 29/1000
s=28, t=4, u=8: 116/1000
s=28, t=4, u=9: 365/1000
s=28, t=4, u=10: 605/1000
s=28, t=4, u=11: 778/1000
s=28, t=4, u=12: 885/1000
s=28, t=4, u=13: 939/1000
s=28, t=4, u=14: 963/1000
s=28, t=6, u=2: 0/1000
s=28, t=6, u=3: 0/1000
s=28, t=6, u=4: 0/1000
s=28, t=6, u=5: 33/1000
s=28, t=6, u=6: 413/1000
s=28, t=6, u=7: 897/1000
s=28, t=6, u=8: 982/1000
s=28, t=8, u=2: 0/1000
s=28, t=8, u=3: 0/1000
s=28, t=8, u=4: 42/1000
s=28, t=8, u=5: 807/1000
s=28, t=8, u=6: 996/1000
s=28, t=10, u=2: 0/1000
s=28, t=10, u=3: 2/1000
s=28, t=10, u=4: 670/1000
s=28, t=10, u=5: 999/1000
s=28, t=12, u=2: 0/1000
s=28, t=12, u=3: 60/1000
s=28, t=12, u=4: 990/1000
s=28, t=14, u=2: 0/1000
s=28, t=14, u=3: 492/1000
s=28, t=14, u=4: 1000/1000
s=28, t=16, u=2: 0/1000
s=28, t=16, u=3: 967/1000
s=28, t=18, u=2: 0/1000
s=28, t=18, u=3: 999/1000
s=28, t=20, u=2: 2/1000
s=28, t=20, u=3: 999/1000
s=28, t=22, u=2: 12/1000
s=28, t=22, u=3: 1000/1000
s=28, t=24, u=2: 72/1000
s=28, t=24, u=3: 1000/1000
s=28, t=26, u=2: 250/1000
s=28, t=26, u=3: 1000/1000
s=28, t=28, u=2: 1000/1000
s=32, t=4, u=2: 0/1000
s=32, t=4, u=3: 0/1000
s=32, t=4, u=4: 0/1000
s=32, t=4, u=5: 0/1000
s=32, t=4, u=6: 1/1000
s=32, t=4, u=7: 2/1000
s=32, t=4, u=8: 21/1000
s=32, t=4, u=9: 93/1000
s=32, t=4, u=10: 250/1000
s=32, t=4, u=11: 500/1000
s=32, t=4, u=12: 684/1000
s=32, t=4, u=13: 826/1000
s=32, t=4, u=14: 900/1000
s=32, t=4, u=15: 936/1000
s=32, t=4, u=16: 944/1000
s=32, t=4, u=17: 952/1000
s=32, t=6, u=2: 0/1000
s=32, t=6, u=3: 0/1000
s=32, t=6, u=4: 0/1000
s=32, t=6, u=5: 6/1000
s=32, t=6, u=6: 86/1000
s=32, t=6, u=7: 580/1000
s=32, t=6, u=8: 935/1000
s=32, t=6, u=9: 982/1000
s=32, t=8, u=2: 0/1000
s=32, t=8, u=3: 0/1000
s=32, t=8, u=4: 4/1000
s=32, t=8, u=5: 285/1000
s=32, t=8, u=6: 978/1000
s=32, t=10, u=2: 0/1000
s=32, t=10, u=3: 0/1000
s=32, t=10, u=4: 145/1000
s=32, t=10, u=5: 989/1000
s=32, t=12, u=2: 0/1000
s=32, t=12, u=3: 3/1000
s=32, t=12, u=4: 901/1000
s=32, t=12, u=5: 999/1000
s=32, t=14, u=2: 0/1000
s=32, t=14, u=3: 63/1000
s=32, t=14, u=4: 999/1000
s=32, t=16, u=2: 0/1000
s=32, t=16, u=3: 493/1000
s=32, t=16, u=4: 1000/1000
s=32, t=18, u=2: 0/1000
s=32, t=18, u=3: 957/1000
s=32, t=20, u=2: 0/1000
s=32, t=20, u=3: 999/1000
s=32, t=22, u=2: 2/1000
s=32, t=22, u=3: 1000/1000
s=32, t=24, u=2: 4/1000
s=32, t=24, u=3: 1000/1000
s=32, t=26, u=2: 13/1000
s=32, t=26, u=3: 1000/1000
s=32, t=28, u=2: 62/1000
s=32, t=28, u=3: 1000/1000
s=32, t=30, u=2: 251/1000
s=32, t=30, u=3: 1000/1000
s=32, t=32, u=2: 1000/1000
s=36, t=2, u=32: 4/1000
s=36, t=4, u=2: 0/1000
s=36, t=4, u=3: 0/1000
s=36, t=4, u=4: 0/1000
s=36, t=4, u=5: 0/1000
s=36, t=4, u=6: 0/1000
s=36, t=4, u=7: 1/1000
s=36, t=4, u=8: 2/1000
s=36, t=4, u=9: 16/1000
s=36, t=4, u=10: 59/1000
s=36, t=4, u=11: 177/1000
s=36, t=4, u=12: 341/1000
s=36, t=4, u=13: 562/1000
s=36, t=4, u=14: 710/1000
s=36, t=4, u=15: 839/1000
s=36, t=4, u=16: 892/1000
s=36, t=4, u=17: 933/1000
s=36, t=4, u=18: 957/1000
s=36, t=6, u=2: 0/1000
s=36, t=6, u=3: 0/1000
s=36, t=6, u=4: 0/1000
s=36, t=6, u=5: 1/1000
s=36, t=6, u=6: 6/1000
s=36, t=6, u=7: 179/1000
s=36, t=6, u=8: 663/1000
s=36, t=6, u=9: 956/1000
s=36, t=8, u=2: 0/1000
s=36, t=8, u=3: 0/1000
s=36, t=8, u=4: 0/1000
s=36, t=8, u=5: 36/1000
s=36, t=8, u=6: 702/1000
s=36, t=8, u=7: 989/1000
s=36, t=10, u=2: 0/1000
s=36, t=10, u=3: 0/1000
s=36, t=10, u=4: 10/1000
s=36, t=10, u=5: 822/1000
s=36, t=10, u=6: 999/1000
s=36, t=12, u=2: 0/1000
s=36, t=12, u=3: 0/1000
s=36, t=12, u=4: 399/1000
s=36, t=12, u=5: 999/1000
s=36, t=14, u=2: 0/1000
s=36, t=14, u=3: 3/1000
s=36, t=14, u=4: 977/1000
s=36, t=16, u=2: 0/1000
s=36, t=16, u=3: 46/1000
s=36, t=16, u=4: 1000/1000
s=36, t=18, u=2: 0/1000
s=36, t=18, u=3: 474/1000
s=36, t=18, u=4: 1000/1000
s=36, t=20, u=2: 0/1000
s=36, t=20, u=3: 955/1000
s=36, t=22, u=2: 0/1000
s=36, t=22, u=3: 996/1000
s=36, t=24, u=2: 0/1000
s=36, t=24, u=3: 1000/1000
s=36, t=26, u=2: 1/1000
s=36, t=26, u=3: 1000/1000
s=36, t=28, u=2: 5/1000
s=36, t=28, u=3: 1000/1000
s=36, t=30, u=2: 16/1000
s=36, t=30, u=3: 1000/1000
s=36, t=32, u=2: 60/1000
s=36, t=32, u=3: 1000/1000
s=36, t=34, u=2: 262/1000
s=36, t=34, u=3: 1000/1000
s=36, t=36, u=2: 1000/1000
s=40, t=4, u=2: 0/1000
s=40, t=4, u=3: 0/1000
s=40, t=4, u=4: 0/1000
s=40, t=4, u=5: 0/1000
s=40, t=4, u=6: 0/1000
s=40, t=4, u=7: 0/1000
s=40, t=4, u=8: 0/1000
s=40, t=4, u=9: 0/1000
s=40, t=4, u=10: 7/1000
s=40, t=4, u=11: 38/1000
s=40, t=4, u=12: 127/1000
s=40, t=4, u=13: 271/1000
s=40, t=4, u=14: 437/1000
s=40, t=4, u=15: 610/1000
s=40, t=4, u=16: 730/1000
s=40, t=4, u=17: 809/1000
s=40, t=4, u=18: 892/1000
s=40, t=4, u=19: 926/1000
s=40, t=4, u=20: 939/1000
s=40, t=4, u=21: 947/1000
s=40, t=4, u=22: 949/1000
s=40, t=4, u=23: 968/1000
s=40, t=6, u=2: 0/1000
s=40, t=6, u=3: 0/1000
s=40, t=6, u=4: 0/1000
s=40, t=6, u=5: 0/1000
s=40, t=6, u=6: 1/1000
s=40, t=6, u=7: 31/1000
s=40, t=6, u=8: 239/1000
s=40, t=6, u=9: 747/1000
s=40, t=6, u=10: 969/1000
s=40, t=8, u=2: 0/1000
s=40, t=8, u=3: 0/1000
s=40, t=8, u=4: 0/1000
s=40, t=8, u=5: 1/1000
s=40, t=8, u=6: 217/1000
s=40, t=8, u=7: 931/1000
s=40, t=8, u=8: 994/1000
s=40, t=10, u=2: 0/1000
s=40, t=10, u=3: 0/1000
s=40, t=10, u=4: 0/1000
s=40, t=10, u=5: 286/1000
s=40, t=10, u=6: 993/1000
s=40, t=12, u=2: 0/1000
s=40, t=12, u=3: 0/1000
s=40, t=12, u=4: 52/1000
s=40, t=12, u=5: 994/1000
s=40, t=14, u=2: 0/1000
s=40, t=14, u=3: 0/1000
s=40, t=14, u=4: 706/1000
s=40, t=14, u=5: 999/1000
s=40, t=16, u=2: 0/1000
s=40, t=16, u=3: 4/1000
s=40, t=16, u=4: 994/1000
s=40, t=18, u=2: 0/1000
s=40, t=18, u=3: 52/1000
s=40, t=18, u=4: 999/1000
s=40, t=20, u=2: 0/1000
s=40, t=20, u=3: 461/1000
s=40, t=20, u=4: 1000/1000
s=40, t=22, u=2: 0/1000
s=40, t=22, u=3: 959/1000
s=40, t=24, u=2: 0/1000
s=40, t=24, u=3: 996/1000
s=40, t=26, u=2: 0/1000
s=40, t=26, u=3: 1000/1000
s=40, t=28, u=2: 1/1000
s=40, t=28, u=3: 1000/1000
s=40, t=30, u=2: 0/1000
s=40, t=30, u=3: 1000/1000
s=40, t=32, u=2: 5/1000
s=40, t=32, u=3: 1000/1000
s=40, t=34, u=2: 12/1000
s=40, t=34, u=3: 1000/1000
s=40, t=36, u=2: 60/1000
s=40, t=36, u=3: 1000/1000
s=40, t=38, u=2: 247/1000
s=40, t=38, u=3: 1000/1000
s=40, t=40, u=2: 1000/1000
s=44, t=4, u=2: 0/1000
s=44, t=4, u=3: 0/1000
s=44, t=4, u=4: 0/1000
s=44, t=4, u=5: 0/1000
s=44, t=4, u=6: 0/1000
s=44, t=4, u=7: 0/1000
s=44, t=4, u=8: 0/1000
s=44, t=4, u=9: 0/1000
s=44, t=4, u=10: 0/1000
s=44, t=4, u=11: 9/1000
s=44, t=4, u=12: 38/1000
s=44, t=4, u=13: 87/1000
s=44, t=4, u=14: 192/1000
s=44, t=4, u=15: 343/1000
s=44, t=4, u=16: 497/1000
s=44, t=4, u=17: 597/1000
s=44, t=4, u=18: 750/1000
s=44, t=4, u=19: 800/1000
s=44, t=4, u=20: 872/1000
s=44, t=4, u=21: 909/1000
s=44, t=4, u=22: 911/1000
s=44, t=4, u=23: 930/1000
s=44, t=4, u=24: 951/1000
s=44, t=6, u=2: 0/1000
s=44, t=6, u=3: 0/1000
s=44, t=6, u=4: 0/1000
s=44, t=6, u=5: 0/1000
s=44, t=6, u=6: 0/1000
s=44, t=6, u=7: 2/1000
s=44, t=6, u=8: 40/1000
s=44, t=6, u=9: 332/1000
s=44, t=6, u=10: 804/1000
s=44, t=6, u=11: 946/1000
s=44, t=6, u=12: 992/1000
s=44, t=8, u=2: 0/1000
s=44, t=8, u=3: 0/1000
s=44, t=8, u=4: 0/1000
s=44, t=8, u=5: 0/1000
s=44, t=8, u=6: 28/1000
s=44, t=8, u=7: 561/1000
s=44, t=8, u=8: 986/1000
s=44, t=10, u=2: 0/1000
s=44, t=10, u=3: 0/1000
s=44, t=10, u=4: 0/1000
s=44, t=10, u=5: 38/1000
s=44, t=10, u=6: 905/1000
s=44, t=10, u=7: 997/1000
s=44, t=12, u=2: 0/1000
s=44, t=12, u=3: 0/1000
s=44, t=12, u=4: 2/1000
s=44, t=12, u=5: 822/1000
s=44, t=12, u=6: 1000/1000
s=44, t=14, u=2: 0/1000
s=44, t=14, u=3: 0/1000
s=44, t=14, u=4: 145/1000
s=44, t=14, u=5: 1000/1000
s=44, t=16, u=2: 0/1000
s=44, t=16, u=3: 0/1000
s=44, t=16, u=4: 913/1000
s=44, t=16, u=5: 1000/1000
s=44, t=18, u=2: 0/1000
s=44, t=18, u=3: 3/1000
s=44, t=18, u=4: 1000/1000
s=44, t=20, u=2: 0/1000
s=44, t=20, u=3: 46/1000
s=44, t=20, u=4: 1000/1000
s=44, t=22, u=2: 0/1000
s=44, t=22, u=3: 475/1000
s=44, t=22, u=4: 1000/1000
s=44, t=24, u=2: 0/1000
s=44, t=24, u=3: 951/1000
s=44, t=26, u=2: 0/1000
s=44, t=26, u=3: 998/1000
s=44, t=28, u=2: 0/1000
s=44, t=28, u=3: 999/1000
s=44, t=30, u=2: 0/1000
s=44, t=30, u=3: 1000/1000
s=44, t=32, u=2: 0/1000
s=44, t=32, u=3: 1000/1000
s=44, t=34, u=2: 0/1000
s=44, t=34, u=3: 1000/1000
s=44, t=36, u=2: 3/1000
s=44, t=36, u=3: 1000/1000
s=44, t=38, u=2: 18/1000
s=44, t=38, u=3: 1000/1000
s=44, t=40, u=2: 75/1000
s=44, t=40, u=3: 1000/1000
s=44, t=42, u=2: 218/1000
s=44, t=42, u=3: 1000/1000
s=44, t=44, u=2: 1000/1000
s=48, t=4, u=2: 0/1000
s=48, t=4, u=3: 0/1000
s=48, t=4, u=4: 0/1000
s=48, t=4, u=5: 0/1000
s=48, t=4, u=6: 0/1000
s=48, t=4, u=7: 0/1000
s=48, t=4, u=8: 0/1000
s=48, t=4, u=9: 0/1000
s=48, t=4, u=10: 0/1000
s=48, t=4, u=11: 1/1000
s=48, t=4, u=12: 4/1000
s=48, t=4, u=13: 20/1000
s=48, t=4, u=14: 66/1000
s=48, t=4, u=15: 164/1000
s=48, t=4, u=16: 253/1000
s=48, t=4, u=17: 361/1000
s=48, t=4, u=18: 508/1000
s=48, t=4, u=19: 594/1000
s=48, t=4, u=20: 711/1000
s=48, t=4, u=21: 791/1000
s=48, t=4, u=22: 816/1000
s=48, t=4, u=23: 882/1000
s=48, t=4, u=24: 902/1000
s=48, t=4, u=25: 911/1000
s=48, t=4, u=26: 928/1000
s=48, t=4, u=27: 949/1000
s=48, t=4, u=28: 947/1000
s=48, t=4, u=29: 948/1000
s=48, t=4, u=30: 970/1000
s=48, t=6, u=2: 0/1000
s=48, t=6, u=3: 0/1000
s=48, t=6, u=4: 0/1000
s=48, t=6, u=5: 0/1000
s=48, t=6, u=6: 0/1000
s=48, t=6, u=7: 0/1000
s=48, t=6, u=8: 4/1000
s=48, t=6, u=9: 86/1000
s=48, t=6, u=10: 426/1000
s=48, t=6, u=11: 815/1000
s=48, t=6, u=12: 952/1000
s=48, t=8, u=2: 0/1000
s=48, t=8, u=3: 0/1000
s=48, t=8, u=4: 0/1000
s=48, t=8, u=5: 0/1000
s=48, t=8, u=6: 4/1000
s=48, t=8, u=7: 155/1000
s=48, t=8, u=8: 853/1000
s=48, t=8, u=9: 993/1000
s=48, t=10, u=2: 0/1000
s=48, t=10, u=3: 0/1000
s=48, t=10, u=4: 0/1000
s=48, t=10, u=5: 3/1000
s=48, t=10, u=6: 479/1000
s=48, t=10, u=7: 993/1000
s=48, t=12, u=2: 0/1000
s=48, t=12, u=3: 0/1000
s=48, t=12, u=4: 0/1000
s=48, t=12, u=5: 304/1000
s=48, t=12, u=6: 995/1000
s=48, t=14, u=2: 0/1000
s=48, t=14, u=3: 0/1000
s=48, t=14, u=4: 12/1000
s=48, t=14, u=5: 992/1000
s=48, t=16, u=2: 0/1000
s=48, t=16, u=3: 0/1000
s=48, t=16, u=4: 374/1000
s=48, t=16, u=5: 1000/1000
s=48, t=18, u=2: 0/1000
s=48, t=18, u=3: 0/1000
s=48, t=18, u=4: 976/1000
s=48, t=20, u=2: 0/1000
s=48, t=20, u=3: 3/1000
s=48, t=20, u=4: 999/1000
s=48, t=22, u=2: 0/1000
s=48, t=22, u=3: 58/1000
s=48, t=22, u=4: 1000/1000
s=48, t=24, u=2: 0/1000
s=48, t=24, u=3: 492/1000
s=48, t=24, u=4: 1000/1000
s=48, t=26, u=2: 0/1000
s=48, t=26, u=3: 959/1000
s=48, t=28, u=2: 0/1000
s=48, t=28, u=3: 998/1000
s=48, t=30, u=2: 0/1000
s=48, t=30, u=3: 1000/1000
s=48, t=32, u=2: 0/1000
s=48, t=32, u=3: 1000/1000
s=48, t=34, u=2: 0/1000
s=48, t=34, u=3: 1000/1000
s=48, t=36, u=2: 1/1000
s=48, t=36, u=3: 1000/1000
s=48, t=38, u=2: 1/1000
s=48, t=38, u=3: 1000/1000
s=48, t=40, u=2: 6/1000
s=48, t=40, u=3: 1000/1000
s=48, t=42, u=2: 12/1000
s=48, t=42, u=3: 1000/1000
s=48, t=44, u=2: 64/1000
s=48, t=44, u=3: 1000/1000
s=48, t=46, u=2: 266/1000
s=48, t=46, u=3: 1000/1000
s=48, t=48, u=2: 1000/1000

なお、元ネタの動画では、s=48, t=4, u=20ですので、10回に7回くらい成功するようです。

また、t=2の場合はuを増やしても成功率がなかなか上がらないようなので、別建てで考察することにしました。

6. おわりに

なぜそうなるのか、の分析は追々。。。（多分何かの論文で出ているはず？）

<追記> CTF Advent Calendar の明日（11日目）の記事は、kam1tsur3さんの「DMくれたよく知らん人とCTF参加してみた | kam1tsur3-web」です。

*1:福山雅治ボイスで再生してください。

*2:sとtに対してuをインクリメントしていきましたが、結果が900/1000以上になった段階で打ち切っています。

Learning cyber security by playing and enjoying CTFs

Cyber Security関係の雑記帳です。表明されているお気持ちなどは全て個人的なものであり、筆者が所属もしくは関係する組織・団体の意向とは一切関係ありません。

Xbitの値Y個からmod(2^Z)のLCGにおける乱数予測する（実験編）