Instantly share code, notes, and snippets.

# hellman/0_mceliece_grs.py

Last active June 23, 2024 12:49
Show Gist options
• Save hellman/eb4b635b32d7f80e16da7e75f93d36df to your computer and use it in GitHub Desktop.
Hack.lu CTF 2017 - McEliece
This file contains bidirectional Unicode text that may be interpreted or compiled differently than what appears below. To review, open the file in an editor that reveals hidden Unicode characters. Learn more about bidirectional Unicode characters
 ''' Attacking McEliece with Generalized Reed-Solomon codes (GRS), method by Sidelnikov & Shestakov. The task is almost the same as The Russian Attack from Sharif CTF: http://ctf.sharif.edu/blog/Write-Ups/SharifCTF-6/Crypto/08.%20The%20Russian%20Attack%20(500%20+%20300%20pts)/ The only change is the field changed from GF(p) to GF(2^8). Here is Sage analogue of the GAP script, because finally Sage supports GRS decoding. ''' from sage.all import * ct = load("ciphertext.sobj") pk = load("publickey.sobj") k, n = pk.dimensions() F = ct[0].parent() M = pk.echelon_form() for c01 in F: if c01 == 0: continue alpha = [None] * n # we can set this w.l.o.g alpha[0] = 0 alpha[1] = 1 # First stage: get alpha[k..n-1] good = 1 for j in xrange(k, n): b01 = M[0,j] / M[1,j] if c01 == b01: good = 0 break alpha[j] = c01 / (c01 - b01) if not good: print c01, ":", "FAIL" continue # Second stage: get alpha[2..k-1] for i in xrange(2, k): p = k q = k + 1 while 1: bp = M[0,p] / M[i,p] bq = M[0,q] / M[i,q] A = bp * (alpha[p] - alpha[0]) A /= bq * (alpha[q] - alpha[0]) if A == 1: p += 1 q += 1 if q == n: break continue alpha[i] = (A * alpha[q] - alpha[p]) / (A - 1) break # if guessed completely if alpha.count(None) == 0: print c01, ":", "Got full alpha." C = codes.GeneralizedReedSolomonCode(alpha, k) D = codes.decoders.GRSBerlekampWelchDecoder(C) try: res = pk.solve_left(D.decode_to_code(ct)) print " ", "message vector:", res msg = "".join(map(chr, [v.integer_representation() for v in res])) print " ", "message:", `msg` except: print "no decoding..."
This file contains bidirectional Unicode text that may be interpreted or compiled differently than what appears below. To review, open the file in an editor that reveals hidden Unicode characters. Learn more about bidirectional Unicode characters
 eJyF1EtwFEUYB3B3syQwQFRAxYAhIGZXhSUJPgIqj0gWzEoMiyMCxnHZ7d0ed3Zme3Y25uFKQPNY BBQVKQ8+Sq3SKq9WWR7Vi1XeLA8etMry7c3y4FH9778zGg6UNZdf99eP7+vumulorpotimTZy9cc UU0WfCEs3bCEI8rCDYxytiSsFAIH2T+ou62icIVv56y8cKvCGus1VCShF6sGfi0X1HyRLGRzgedP GOHYhbZVcyt2ruQIQ0WvOMfxvFKtYhUd70TWMVSLafyXg4rNZNSSdFs6NqtaEzKakC3m8pTt2oFI 2cLJqzbEl8rWhcV92y1Wk7YbiKLwdT1hQy0zo/09GG2Y0cl+tXzxhIrnTLhe2c46i2gVC33jeo3w gNSK/5/VjFk5z9V1er4x8m8sg5ChVrKMZs5ymRnpQ0btZmR8Rl09bMZwIa66xoxO1WV7M9qL6LXz gVpVD9TqjFqDgcONIKOuG1XXX1ZygUdiXVZ/83oNHKOhbgjXWhtueaNcM5dRHZKR5qmsk7prvezg t55fh2g05mYz6iaztWiPZX1PdZqdU/GKLwr2eHxnV3wyvqUr7ouK32xg33g93GFDeikS76qrjQmz VU9Qm8zIpBlrDlc3my0YrjbXAnVLRnWnpxvDgYqjzERG3TqqbrtydSJ8lkzICF+YtehVLMQGw2u7 XXanf0IZW2RTx6Ct1FtQkjoEbaN6oB7qB6iX+gbqo/ZD26kPoTuoAehOqh26i7oE3U0NQf1Sj9wG 76BaoJ3UL9A9Uq/+Onwv5UP3Ub9Du6jV0G7KhvZQR6G91D5ogHoTul/qdS7C+6j3oUFqD5SiPob2 UzHoAPUa9AC1DhqifobS1BHowYVs2+CDlAENU/PQQ9S30Aj1F3SI6ocyVAo6TBWhh6XOJwqb1CfQ I9RV0BFqDHqUMqGjVBI6Rp2FjlO7oMeod6BR6hT0OPU1ZFET0BPUCJSVQ1Ln9iNaJ6g/oBzlQnnq M0hQX0AFKg8VMV/3x9GS1GHIps5BT1K/QSWpvQp2pD6HlXCZOgm5VCfkSU8OYLw+wbfRU6G2Qopa C/nUaahKbYcC6jxUo36FxqjvoacoBY1T70IT1BJoktoNTVHvQU9THVBdlujj8DPUR9BJ6k9oWuqX thc+RSWg09Qg9Cy1A3qOWgHNSH2PEXiW+huao0aheeo7qEF9BZ2Res9u+HlqM3SW2gSdowR0nvoc eoG6AL1IfQpdoCzoJanf8Rvwy9SX0CtS/xs+gC9SB6BXRXp6Hj/jS8l/ACTDlyA=
This file contains bidirectional Unicode text that may be interpreted or compiled differently than what appears below. To review, open the file in an editor that reveals hidden Unicode characters. Learn more about bidirectional Unicode characters