#lll

68바이트 플래그를 34바이트씩 fl과 ag로 자른 뒤 fl, ag, 그리고 원본 flag를 같은 RSA 키로 전부 암호화해 공개한 문제. 평문 사이에 남은 일차 관계를 비 하나로 접어 Franklin-Reiter 관련 메시지 공격을 태우고, 거기서 나온 비를 2차원 격자 축약으로 다시 두 조각으로 펴서 0.9초 만에 플래그를 복원한 과정을 정리했다.

서명 20개와 각 서명의 nonce 상위 16비트가 주어지는 ECDSA 문제. 사이드채널 유출이라는 말에 반사적으로 격자를 떠올리기 쉽지만, 데이터를 먼저 재 보면 nonce 자체가 32비트뿐이라 미지수가 16비트밖에 안 남는다. 서명 하나로 65,536개의 개인키 후보를 만들고 나머지 19개 서명으로 걸러 내면 후보가 정확히 하나로 줄어든다. 복구한 키는 직접 구현한 secp160r1 과 SageMath 두 곳에서 공개키를 다시 만들어 서명 20개를 전부 검증했고, 정석인 Hidden Number Problem 격자로도 같은 값이 나오는지 LLL 로 교차 확인했다.

RSA 소수 p 의 상위 744비트가 그대로 노출된 문제. Coppersmith 의 known-MSB 인수분해를 3x3 격자로 직접 짜서 하위 280비트를 되찾고, 순수 파이썬 LLL 만으로 0.4초 만에 n 을 쪼갠다. SageMath small_roots 와 openssl 로 교차검증까지.

flag 를 f·l·ag 세 조각으로 쪼개 각각·전체를 e=257 RSA 로 암호화한 문제. Franklin–Reiter 와 Gröbner 가 막히는 지점을 짚고, ℤ/N 위에서 monic 없이 변수를 소거하는 의사 나눗셈으로 비율 f/ag, l/ag 를 뽑은 뒤 LLL 로 평문을 복원한다.