Midnight Sun CTF 2019 Quals - open-gyckel-krypto

0_sol.ipynb

{
 "cells": [
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "In this challenge we have an RSA modulus that can expressed as\n",
    "\n",
    "$$n = (10^{250} a + b) (10^{250} b+a),$$ where $a,b$ are less than $10^{250}$.\n",
    "\n",
    "$$n = 10^{500}ab + 10^{250}(a^2+b^2) + ab.$$\n",
    "\n",
    "The trick to solve it is to look at the modulus modulo $10^{250}, 10^{500}, 10^{750}$. First, \n",
    "\n",
    "$$n \\equiv ab \\pmod{10^{250}}.$$\n",
    "\n",
    "However, we don't know full ab from here, because of the overflow. However, we can learn the high part of it from the term $10^{500}ab$. Indeed, \n",
    "\n",
    "$$10^{250}(a^2+b^2) < 2\\cdot10^{750},~\\text{and}$$\n",
    "\n",
    "$$\\lfloor n / 10^{750}\\rfloor = ab/10^{250} + e,~\\text{where}~ 0 <= e <= 2.$$\n",
    "\n",
    "Together with $ab \\mod 10^{250}$, we learn full $ab$, denote it by $c$. Then \n",
    "\n",
    "$$n - 10^{500}c - c = 10^{250}(a^2+b^2) = 10^{250}(a^2+(c/a)^2).$$\n",
    "\n",
    "We get a quartic equation on a over integers, which is actually a quadratic equation on $a^2$. By solving it, we factor $n$.\n"
   ]
  }
 ],
 "metadata": {
  "kernelspec": {
   "display_name": "Python 2",
   "language": "python",
   "name": "python2"
  }
 },
 "nbformat": 4,
 "nbformat_minor": 2
}

1_chall.txt

while True:
    p = next_prime(random.randint(0, 10**500))
    if len(str(p)) != 500:
        continue
    q = Integer(int(str(p)[250:] + str(p)[:250]))
    if q.is_prime():
        break

>> p * q
6146024643941503757217715363256725297474582575057128830681803952150464985329239705861504172069973746764596350359462277397739134788481500502387716062571912861345331755396960400668616401300689786263797654804338789112750913548642482662809784602704174564885963722422299918304645125966515910080631257020529794610856299507980828520629245187681653190311198219403188372517508164871722474627810848320169613689716990022730088459821267951447201867517626158744944551445617408339432658443496118067189012595726036261168251749186085493288311314941584653172141498507582033165337666796171940245572657593635107816849481870784366174740265906662098222589242955869775789843661127411493630943226776741646463845546396213149027737171200372484413863565567390083316799725434855960709541328144058411807356607316377373917707720258565704707770352508576366053160404360862976120784192082599228536166245480722359263166146184992593735550019325337524138545418186493193366973466749752806880403086988489013389009843734224502284325825989
>> pow(m, 65537, p * q)
3572030904528013180691184031825875018560018830056027446538585108046374607199842488138228426133620939067295245642162497675548656988031367698701161407333098336631469820625758165691216722102954230039803062571915807926805842311530808555825502457067483266045370081698397234434007948071948000301674260889742505705689105049976374758307610890478956315615270346544731420764623411884522772647227485422185741972880247913540403503772495257290866993158120540920089734332219140638231258380844037266185237491107152677366121632644100162619601924591268704611229987050199163281293994502948372872259033482851597923104208041748275169138684724529347356731689014177146308752441720676090362823472528200449780703866597108548404590800249980122989260948630061847682889941399385098680402067366390334436739269305750501804725143228482932118740926602413362231953728010397307348540059759689560081517028515279382023371274623802620886821099991568528927696544505357451279263250695311793770159474896431625763008081110926072287874375257

2_solve.py

#-*- coding:utf-8 -*-

from sage.all import *
from libnum import *

CT = 3572030904528013180691184031825875018560018830056027446538585108046374607199842488138228426133620939067295245642162497675548656988031367698701161407333098336631469820625758165691216722102954230039803062571915807926805842311530808555825502457067483266045370081698397234434007948071948000301674260889742505705689105049976374758307610890478956315615270346544731420764623411884522772647227485422185741972880247913540403503772495257290866993158120540920089734332219140638231258380844037266185237491107152677366121632644100162619601924591268704611229987050199163281293994502948372872259033482851597923104208041748275169138684724529347356731689014177146308752441720676090362823472528200449780703866597108548404590800249980122989260948630061847682889941399385098680402067366390334436739269305750501804725143228482932118740926602413362231953728010397307348540059759689560081517028515279382023371274623802620886821099991568528927696544505357451279263250695311793770159474896431625763008081110926072287874375257
n = 6146024643941503757217715363256725297474582575057128830681803952150464985329239705861504172069973746764596350359462277397739134788481500502387716062571912861345331755396960400668616401300689786263797654804338789112750913548642482662809784602704174564885963722422299918304645125966515910080631257020529794610856299507980828520629245187681653190311198219403188372517508164871722474627810848320169613689716990022730088459821267951447201867517626158744944551445617408339432658443496118067189012595726036261168251749186085493288311314941584653172141498507582033165337666796171940245572657593635107816849481870784366174740265906662098222589242955869775789843661127411493630943226776741646463845546396213149027737171200372484413863565567390083316799725434855960709541328144058411807356607316377373917707720258565704707770352508576366053160404360862976120784192082599228536166245480722359263166146184992593735550019325337524138545418186493193366973466749752806880403086988489013389009843734224502284325825989
T = 250

ablo = n % 10**T
abhi = (n - ablo) // 10**(3*T)

x = PolynomialRing(QQ, names='x').gen()
for delta in xrange(3):
    c = (abhi - delta) * 10**T + ablo
    poly = 10**(2*T)*c*x**2 + 10**T*(x**4 + c**2) + c*x**2 - n*x**2
    for a, m in poly.roots():
        print "delta", delta, "root", a
        b = c / a
        p = 10**T*a+b
        q = 10**T*b+a

        d = inverse_mod(0x10001, (p-1)*(q-1))
        print `n2s(int(pow(CT, d, n)))`
        quit()

#midnight{w3ll_wh47_d0_y0u_kn0w_7h15_15_4c7u4lly_7h3_w0rld5_l0n6357_fl46_4nd_y0u_f0und_17_50_y0u_5h0uld_b3_pr0ud_0f_y0ur53lf_50_uhmm_60_pr1n7_7h15_0n_4_75h1r7_0r_50m37h1n6_4nd_4m4z3_7h3_p30pl3_4r0und_y0u}