Shiho Midorikawa elliptic-shiho

## solve.sage
"""
Google CTF 2024 Quals: mceliece

References:

1. V. M. Sidelinkov and S. O. Shestakov. 1992. "On insecurity of cryptosystems based on generalized Reed-Solomon codes".
2. C. Wischebrink. 2009. "Cryptanalysis of the Niederreiter Public Key Scheme Based on GRS Subcodes".
3. A. Couvreur, P. Gaborit, V. Gauthier-Umaña, A. Otmani, and Jean-Pierre Tillich. 2013 (revised at 2014). "Distinguisher-Based Attacks on Public-Key Cryptosystems Using Reed-Solomon Codes".
4. A. Otmani and H. T. Kalachi. 2015. "Square Code Attack on a Modified Sidelnikov Cryptosystem".
"""

## solve.py
from socket import create_connection
import itertools
import binascii
import struct
import json
import math


class Tube:
    def __init__(s, host, port, debug=False):

## solve.sage
import sys

m = 12
t = 171

_z12, _x = var("_z12, _x")
dataset = open('output.txt').read().strip().replace('^', '**').split('\n')
F.<z12> = GF(2^m)
R.<x> = F['x']
f = eval(dataset[0].lstrip('f = '))

## solve.sage
import binascii

u = 1462429177173255359388007765931796537885368646963625242711326952977985471932962383861842635724040143033586225507124897993946275538644782337485276659791768803892242293535522679957964876776825548307042572518152706215000123872096447939862588392736653305289270336986724756913886373602016050815040147667630379593859685646307913471020561969933852495456652645591262189417744078633139731004839760821762709078987432999550663454348821414654652257866073987807333618308663409376712742627162896125313056171829232263020741802783450992451834392620606043876037571745527804406103083287186596413204262417693475997360716169601004
v = 3361480002432693752626969088049143371033687796839032797315025143270946165139685061767026950394284498430926616845318237749712235930625309923903553850166793512181385788796869552215035455995370731816925378753732950039662516557875218374075823193808692392905081204067496016151667029418998917540743277631790419809752354652686500452367372802836483170592925224959479584778030250914074383997961924

## solve.sage
from socket import create_connection


class Tube:
    def __init__(s, host, port, debug=False):
        s.host = host
        s.port = port
        s.sock = create_connection((host, port))
        s.debug = debug

## solve_log
Sun Oct  8 02:57:45 JST 2023 ~/Downloads/many_time_qkd
> time python solve_with_bruteforce.py
[+] Getting distribution...
[*] Done: defaultdict(<function solve.<locals>.<lambda> at 0x7faaa91104a0>, {0: [5, 19], 1: [5, 19], 2: [8, 16], 3: [19, 5], 4: [23, 1], 5: [3, 21], 6: [23, 1], 7: [8, 16], 8: [4, 20], 9: [22, 2], 10: [2, 22], 11: [5, 19], 12: [20, 4], 13: [20, 4], 14: [2, 22], 15: [3, 21], 16: [2, 22], 17: [21, 3], 18: [21, 3], 19: [19, 5], 20: [4, 20], 21: [21, 3], 22: [16, 8], 23: [0, 24]})
[+] ok = [1, 1, 1, 0, 0, 1, 0, 1, 1, 0, 1, 1, 0, 0, 1, 1, 1, 0, 0, 0, 1, 0, 0, 1]
[+] Getting distribution...
[*] Done: defaultdict(<function solve.<locals>.<lambda> at 0x7faaa9110540>, {0: [1, 23], 1: [4, 20], 2: [4, 20], 3: [8, 16], 4: [21, 3], 5: [2, 22], 6: [21, 3], 7: [22, 2], 8: [21, 3], 9: [2, 22], 10: [1, 23], 11: [3, 21], 12: [21, 3], 13: [22, 2], 14: [2, 22], 15: [3, 21], 16: [2, 22], 17: [21, 3], 18: [20, 4], 19: [21, 3], 20: [20, 4], 21: [5, 19], 22: [22, 2], 23: [17, 7]})
[+] ok = [1, 1, 1, 0, 0, 1, 0,

## seccamp 2023 講師参加記.md

      
              1 file
            
          
              0 forks
            
          
              0 comments
            
          
              0 stars
            
          
                elliptic-shiho
                / seccamp 2023 講師参加記.md
            
            
              Last active
              August 14, 2023 18:25
            
          
    seccamp 2023 講師参加記

セキュリティキャンプにL1 暗号化通信ゼミ講師として参加していました. しばらくキャンプ関連の記事は書いていなかったのですが, 久々のオフライン開催の後ということもあり, とりあえず書いてみようかなと思う次第です.
プロトコルコースを含めL1全体の方針は同じくL1講師をされていた @tex2e さんの参加記( https://tex2e.github.io/blog/misc/seccamp2023 )によくまとめられているので, この記事ではその点を端折ったプリミティブコース側の視点をメインとしています. なのでこちらも合わせて読んでいただけますとより一層「L1ゼミというゼミは何をやっていたのか」を理解いただけるのではないでしょうか.
私達の担当したL1ゼミは2コースに分かれており, 私は特にプリミティブコースという極めて理論に近いコースを担当させていただきました. その目標設定は大目標である当該論文の全体理解 + 読み進める・実装する上での小目標をその都度, という形で実施しました. また, 小目標のステップを可能な限り小さくとり, それによって漸進的に進めることを考えました.
TL; DR 来年度の受講を考えている方へ

そもそも来年私が講師として呼ばれる保証がない, ということを念頭に置いてください. セキュリティ・キャンプの講師は基本一年単位なのです.

  
## precomputation_log.md

      
              1 file
            
          
              0 forks
            
          
              1 comment
            
          
              0 stars
            
          
                elliptic-shiho
                / precomputation_log.md
            
            
              Created
              July 9, 2023 08:09
            
          
    mode=0


ell=16

ai=[20, 114, 184, 221, 121, 1, 4, 0, 3, 0, 0, 1, 2, 2, 3, 2]
bi=[0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0]
Hash: 1768495365


ell=17

ai=[129, 141, 66, 239, 178, 1, 2, 2, 1, 0, 2, 3, 2, 0, 3, 1, 0]
bi=[0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0]
Hash: 4117914335


ell=18


## solve.sage
from sage.all import *
import output
import binascii

p = 7690745050590286968025665448815927548186441771518218204702842288098845344789340509868897149374937793107491606741591691437711395848517107039674900831427939
q = 9397241380094769307017158485931177341961951476061947013977394739417988689050439874435488908822482074028128151771446818457295188445665208696820950505470967


def compute_t(F, c, a):
    cf = F(c)

## solve.sage
from sage.all import *
from Crypto.Util.number import long_to_bytes

A = 6737149052150272134972940516590980024331491319339741317342183169802474656888386084365871287308045730462954100927849817850868865189752921007067826413968051476282853264469660023301658697080152738648906257793188559177506701773637608811467111764155767760049813836531589499517889064750007039677591074035963533567
q = 15040222622096320078383580808680733765955114958694997949647342925417877088612792495485641348591026281373930569798925789027166056695954731923306109646611840570310396750856642056018981080439916663195842593441587057719678555907050674529272376248049062724657792390788687452049496308886252188791975094655675938807

F = GF(q)
PR.<x> = F[x]
l = (x ^ 6 - A).roots()
for a, b in l:
	"""
	Google CTF 2024 Quals: mceliece

	References:

	1. V. M. Sidelinkov and S. O. Shestakov. 1992. "On insecurity of cryptosystems based on generalized Reed-Solomon codes".
	2. C. Wischebrink. 2009. "Cryptanalysis of the Niederreiter Public Key Scheme Based on GRS Subcodes".
	3. A. Couvreur, P. Gaborit, V. Gauthier-Umaña, A. Otmani, and Jean-Pierre Tillich. 2013 (revised at 2014). "Distinguisher-Based Attacks on Public-Key Cryptosystems Using Reed-Solomon Codes".
	4. A. Otmani and H. T. Kalachi. 2015. "Square Code Attack on a Modified Sidelnikov Cryptosystem".
	"""
	from socket import create_connection
	import itertools
	import binascii
	import struct
	import json
	import math


	class Tube:
	def __init__(s, host, port, debug=False):
	import sys

	m = 12
	t = 171

	_z12, _x = var("_z12, _x")
	dataset = open('output.txt').read().strip().replace('^', '**').split('\n')
	F.<z12> = GF(2^m)
	R.<x> = F['x']
	f = eval(dataset[0].lstrip('f = '))
	import binascii

	u = 1462429177173255359388007765931796537885368646963625242711326952977985471932962383861842635724040143033586225507124897993946275538644782337485276659791768803892242293535522679957964876776825548307042572518152706215000123872096447939862588392736653305289270336986724756913886373602016050815040147667630379593859685646307913471020561969933852495456652645591262189417744078633139731004839760821762709078987432999550663454348821414654652257866073987807333618308663409376712742627162896125313056171829232263020741802783450992451834392620606043876037571745527804406103083287186596413204262417693475997360716169601004
	v = 3361480002432693752626969088049143371033687796839032797315025143270946165139685061767026950394284498430926616845318237749712235930625309923903553850166793512181385788796869552215035455995370731816925378753732950039662516557875218374075823193808692392905081204067496016151667029418998917540743277631790419809752354652686500452367372802836483170592925224959479584778030250914074383997961924
	Sun Oct 8 02:57:45 JST 2023 ~/Downloads/many_time_qkd
	> time python solve_with_bruteforce.py
	[+] Getting distribution...
	[*] Done: defaultdict(<function solve.<locals>.<lambda> at 0x7faaa91104a0>, {0: [5, 19], 1: [5, 19], 2: [8, 16], 3: [19, 5], 4: [23, 1], 5: [3, 21], 6: [23, 1], 7: [8, 16], 8: [4, 20], 9: [22, 2], 10: [2, 22], 11: [5, 19], 12: [20, 4], 13: [20, 4], 14: [2, 22], 15: [3, 21], 16: [2, 22], 17: [21, 3], 18: [21, 3], 19: [19, 5], 20: [4, 20], 21: [21, 3], 22: [16, 8], 23: [0, 24]})
	[+] ok = [1, 1, 1, 0, 0, 1, 0, 1, 1, 0, 1, 1, 0, 0, 1, 1, 1, 0, 0, 0, 1, 0, 0, 1]
	[+] Getting distribution...
	[*] Done: defaultdict(<function solve.<locals>.<lambda> at 0x7faaa9110540>, {0: [1, 23], 1: [4, 20], 2: [4, 20], 3: [8, 16], 4: [21, 3], 5: [2, 22], 6: [21, 3], 7: [22, 2], 8: [21, 3], 9: [2, 22], 10: [1, 23], 11: [3, 21], 12: [21, 3], 13: [22, 2], 14: [2, 22], 15: [3, 21], 16: [2, 22], 17: [21, 3], 18: [20, 4], 19: [21, 3], 20: [20, 4], 21: [5, 19], 22: [22, 2], 23: [17, 7]})
	[+] ok = [1, 1, 1, 0, 0, 1, 0,
	from sage.all import *
	import output
	import binascii

	p = 7690745050590286968025665448815927548186441771518218204702842288098845344789340509868897149374937793107491606741591691437711395848517107039674900831427939
	q = 9397241380094769307017158485931177341961951476061947013977394739417988689050439874435488908822482074028128151771446818457295188445665208696820950505470967


	def compute_t(F, c, a):
	cf = F(c)
	from sage.all import *
	from Crypto.Util.number import long_to_bytes

	A = 6737149052150272134972940516590980024331491319339741317342183169802474656888386084365871287308045730462954100927849817850868865189752921007067826413968051476282853264469660023301658697080152738648906257793188559177506701773637608811467111764155767760049813836531589499517889064750007039677591074035963533567
	q = 15040222622096320078383580808680733765955114958694997949647342925417877088612792495485641348591026281373930569798925789027166056695954731923306109646611840570310396750856642056018981080439916663195842593441587057719678555907050674529272376248049062724657792390788687452049496308886252188791975094655675938807

	F = GF(q)
	PR.<x> = F[x]
	l = (x ^ 6 - A).roots()
	for a, b in l: