bh-chaker/README.md

## README.md

      
    Raw
  

              README.md
            
          
    The source code of the server code was given.

It just generates an RSA key and sends us some information:
    N, delta, gamma = gen_key()

    m = int(FLAG.encode('hex'), 16)
    c = powmod(m, 0x10001, N)

    print introduction
    print 'N = {}'.format(N)
    print 'delta = {}'.format(delta)
    print 'gamma = {}'.format(gamma)
    print 'ciphertext = {}'.format(c)
Here is the function gen_key:
def gen_key():
    t1 = randint(768, 928)
    t2 = 1024 - t1

    if t1 > t2:
        t1, t2 = t2, t1
    assert t1 < t2

    p2 = pad(getrandbits(1024 - t2) << t2, 1024)
    p0 = pad(getrandbits(t1), t1)

    q2 = pad(getrandbits(1024 - t2) << t2, 1024)
    q0 = pad(getrandbits(t1), t1)

    r = pad(getrandbits(t2 - t1) << t1, t2)

    p = next_prime((p2 ^ r ^ p0))
    q = next_prime((q2 ^ r ^ q0))

    N = p * q

    return N, t2 - t1, p0 - q0 
So, we are given N and (p0-q0). Knowing p and q share the same middle bits r,

we can deduce this relation:


Note:

gamma is different from (p-q) mod 2**t2 because of the calls to next_prime.

We need to brute force a small offset.

Here I chose the offset to have a maximum of 1000.

Next, we use this identity to get a square modulo power of two:


You can read about the problem of "square root modulo power of two" in section 2.3 of this document: LSBSRSA.pdf
I found a C++ implement for the more general problem "square root modulo N": Square-Root-Modulo-N
Then, I translated the part where it does power of two to python: power_of_two
def sqrt_mod_power_of_two(a, k):
    if a % min(2**k, 8) == 1:
        if k == 1:
            return [1]
        elif k == 2:
            return [1, 3]
        elif k == 3:
            return [1, 3, 5, 7]
        else:
            # Small optimization for the case of a == 1.
            if a == 1:
                return [1, 2**(k-1) - 1, 2**(k-1) + 1, 2**k - 1]
            else:
                roots = []
                for x in sqrt_mod_power_of_two(a, k-1):
                    i = 1 if ((x*x - a) >> (k - 1)) % 2 == 1 else 0
                    r = x + i*(1 << (k - 2))
                    roots.append(r)
                    roots.append(2**k - r)
                return list(set(roots))
    return []
The quantity N+((p+q)/2)**2 is not always congruent to 1 modulo 8.

But we are sure to get a nice problem in less than 10 tries.
Now, after solving the "square root modulo power of 2" problem, we have (p+q)/2 and (p-q)/2 mod 2**t2.

We take the sum and get the value of p mod 2**t2.

We are left with only t1 bits missing from p.

Knowing that t2 is at least 768 and t1 is at most 1024-768=256,

we can simply use Coppersmith's method (the function small_roots in SageMath):
def solve_problem(N, delta, gamma):
    t2 = (delta + 1024)/2
    t1 = 1024-t2
    tt2 = 2**t2
    F.<x> = PolynomialRing(Zmod(N), implementation='NTL')

    for i in xrange(-512, 512):
        diff = gamma//2 + i
        d = (N+diff**2)%tt2
        for r in sqrt_mod_power_of_two(d, t2):
            p0 = r + diff

            # Coppersmith
            pol = x*tt2 + p0
            for root in pol.monic().small_roots(X=2**t1, beta=0.5):
                p = int(root)*tt2 + p0
                q = N // p
                if p<N and q<N and p*q == N:
                    return p, q
    return 0, 0
When the problem fits the criteria for solving the "square root modulo power of two" part,

we get p and q in less than a minute.

The flag for this task was:

MeePwnCTF{It_is_the_time_to_move_to_Post_Quantum_Cryptography_DAGS}

  
## equation_1.png

      
    Raw
  

              equation_1.png
            
          
## equation_2.png

      
    Raw
  

              equation_2.png
            
          
## midbit.py
#!/usr/bin/env python2

from flag import FLAG
from gmpy2 import next_prime, powmod
from random import randint, getrandbits
from hashlib import sha512, sha256
from os import urandom

introduction = """
 .--.     .-------------------------------.
 | _|     |                               |
 | O O   <  Hey man, wanna mid some bit ? |
 |  |  |  |                               |
 || | /   `-------------------------------'
 |`-'|
 `---'
Whoever says live is simple, is the one never actually live. :))
"""


def pad(num, length):
    result = bin(num).lstrip('0b').strip('L')
    result = result + '0' * (length - len(result))
    return int(result, 2)


def xor(a, b):
    return ''.join(chr(ord(i) ^ ord(j)) for i, j in zip(a, b))


def gen_key():
    t1 = randint(768, 928)
    t2 = 1024 - t1

    if t1 > t2:
        t1, t2 = t2, t1
    assert t1 < t2

    p2 = pad(getrandbits(1024 - t2) << t2, 1024)
    p0 = pad(getrandbits(t1), t1)

    q2 = pad(getrandbits(1024 - t2) << t2, 1024)
    q0 = pad(getrandbits(t1), t1)

    r = pad(getrandbits(t2 - t1) << t1, t2)

    p = next_prime((p2 ^ r ^ p0))
    q = next_prime((q2 ^ r ^ q0))

    N = p * q

    return N, t2 - t1, p0 - q0


def proof_of_shit():
    """
    This function has very special purpose
    :)) Simply to screw you up
    """
    raw = urandom(6)
    print 'prefix = {}'.format(raw.encode('hex'))
    challenge = raw_input('Challenge: ')
    temp = sha256(raw + challenge).hexdigest()
    if temp.startswith('25455'):
        return True
    else:
        return False


if __name__ == "__main__":
    try:
        assert proof_of_shit() == True
        N, delta, gamma = gen_key()

        m = int(FLAG.encode('hex'), 16)
        c = powmod(m, 0x10001, N)

        print introduction
        print 'N = {}'.format(N)
        print 'delta = {}'.format(delta)
        print 'gamma = {}'.format(gamma)
        print 'ciphertext = {}'.format(c)

    except AssertionError:
        print "Take your time and think of the inputs."

## solver_midbit.sage
import sys, time, socket, itertools, string
from hashlib import sha256

def wait4string(s, p1, p2=None, verbose=True):
    line = ""
    while line.find(p1) == -1 and (p2==None or line.find(p2) == -1):
        try:
            c = s.recv(1)
        except:
            return False
        line += c
        if verbose:
            sys.stdout.write(c)

    return line

def receive_value(s, prompt, delimiter='\n'):
    wait4string(s, prompt)
    return wait4string(s, delimiter)[:-len(delimiter)]

def send_value(s, prompt, value):
    wait4string(s, prompt)
    s.send(value + '\n')


def sqrt_mod_power_of_two(a, k):
    if a % min(2**k, 8) == 1:
        if k == 1:
            return [1]
        elif k == 2:
            return [1, 3]
        elif k == 3:
            return [1, 3, 5, 7]
        else:
            # Small optimization for the case of a == 1.
            if a == 1:
                return [1, 2**(k-1) - 1, 2**(k-1) + 1, 2**k - 1]
            else:
                roots = []
                for x in sqrt_mod_power_of_two(a, k-1):
                    i = 1 if ((x*x - a) >> (k - 1)) % 2 == 1 else 0
                    r = x + i*(1 << (k - 2))
                    roots.append(r)
                    roots.append(2**k - r)
                return list(set(roots))
    return []

def solve_problem(N, delta, gamma):
    t2 = (delta + 1024)/2
    t1 = 1024-t2
    tt2 = 2**t2
    F.<x> = PolynomialRing(Zmod(N), implementation='NTL')

    for i in xrange(-512, 512):
        diff = gamma//2 + i
        d = (N+diff**2)%tt2
        for r in sqrt_mod_power_of_two(d, t2):
            p0 = r + diff

            # Coppersmith
            pol = x*tt2 + p0
            for root in pol.monic().small_roots(X=2**t1, beta=0.5):
                p = int(root)*tt2 + p0
                q = N // p
                if p<N and q<N and p*q == N:
                    return p, q
    return 0, 0

def proof_of_shit(prefix):
    raw = prefix.decode('hex')
    for i in itertools.product(string.letters+string.digits, repeat=4):
        challenge = ''.join(i)
        temp = sha256(raw + challenge).hexdigest()
        if temp.startswith('25455'):
            return challenge

def get_problem():
    s = socket.socket(socket.AF_INET, socket.SOCK_STREAM)
    s.connect(("206.189.92.209", 54321))

    prefix = receive_value(s, 'prefix = ')
    send_value(s, 'Challenge: ', proof_of_shit(prefix))

    N = int(receive_value(s, 'N = '))
    delta = int(receive_value(s, 'delta = '))
    gamma = int(receive_value(s, 'gamma = '))
    ciphertext = int(receive_value(s, 'ciphertext = '))

    s.close()

    return N, delta, gamma, ciphertext


sample_problems = [
(
    15371749866237646115508350356898072838537706952391263995555938638047512678091547244203379619608626117145212393724653366844752912720621272630141104163458987208064224796167760681043609656284983064426906662893810537320759009783797365080443517944804822707110263161312712740531410411367077103880944521615766398260374415077209037087676578198874509696761864256422299034723840926476366300225520343114927960534284655773996239468008535568776610233953412608042280531797807629722936969010048012255071342744012000262917695278464764342270298361144557893988456450145602415009910229045627863895652984430726880017939957843077135659981,
    564,
    -226299809893849590679441637878369498170874625024638560035914727717118,
    11802632707469573162754173541723445984727582220532965265187609906624038778440270519007571058513140673836179915789232852062150201090926597762810016612939361857580886357121011036542374138868580118230073003496642061470679118663117958022026286699914114637244392685482016550549362473841731417155449455351004539276253989018353281271041423374747038709963100599328059487602428824624557579487442597571103992082843021211283772250686916208840355682507963995060485746870359907102129092007862324533411821101867166147674696760187305327376572128510450857755389172556570031706299891092461249816759961779896520947976331742402773075971
),
(
    27571714022630446692205953100246158492104343818129988455758841100800625908329333049812739488534462547281844187880398858752988120705023176776864297511150663619838138626463727122379270088400616428090232830742536890594530487104023780828515169390630286507171033349382225851792980779029965551410119688014838349603230898762802400667244753623403321601517381122132390779455117662264884559525989873640369124355635142220605076029195039341204090577775284758044852508497431261501801774855305788831726565284052375319823081318241303764980093775693900244699784207847658928057210652673501693218497434631625025906040696515446860476313,
    756,
    -1653388744922225434552735986983871360024,
    5638442668480888261640815459781493637271722451633604058526896568348240873974558692467763006225556555199628842538772844043373056249640522719865568364801926391725178640151594865198391904566873806087272052870989078290742545776876474857803824726823211561499369207875202657008341950317589422211493894328981517532660461327247474364787809590589769887989664336482960709851897616673604569569320051687427587493177756239065743745105737456246338933101315533661411929907477377965609507224875416678635297515237594695926117719526744022861218005930819335477380455720839871924821520965155085348952181664215868632028643750071764326129
)
]

# N, delta, gamma, ciphertext = sample_problems[0]
N, delta, gamma, ciphertext = get_problem()

p, q = solve_problem(N, delta, gamma)
if p*q == N:
    d = int(inverse_mod(0x10001, (p-1)*(q-1)))
    m = pow(ciphertext, d, N)

    print ('%x'%m).decode('hex')
	#!/usr/bin/env python2

	from flag import FLAG
	from gmpy2 import next_prime, powmod
	from random import randint, getrandbits
	from hashlib import sha512, sha256
	from os import urandom

	introduction = """
	.--. .-------------------------------.
	\| _\| \| \|
	\| O O < Hey man, wanna mid some bit ? \|
	\| \| \| \| \|
	\|\| \| / `-------------------------------'
	\|`-'\|
	`---'
	Whoever says live is simple, is the one never actually live. :))
	"""


	def pad(num, length):
	result = bin(num).lstrip('0b').strip('L')
	result = result + '0' * (length - len(result))
	return int(result, 2)


	def xor(a, b):
	return ''.join(chr(ord(i) ^ ord(j)) for i, j in zip(a, b))


	def gen_key():
	t1 = randint(768, 928)
	t2 = 1024 - t1

	if t1 > t2:
	t1, t2 = t2, t1
	assert t1 < t2

	p2 = pad(getrandbits(1024 - t2) << t2, 1024)
	p0 = pad(getrandbits(t1), t1)

	q2 = pad(getrandbits(1024 - t2) << t2, 1024)
	q0 = pad(getrandbits(t1), t1)

	r = pad(getrandbits(t2 - t1) << t1, t2)

	p = next_prime((p2 ^ r ^ p0))
	q = next_prime((q2 ^ r ^ q0))

	N = p * q

	return N, t2 - t1, p0 - q0


	def proof_of_shit():
	"""
	This function has very special purpose
	:)) Simply to screw you up
	"""
	raw = urandom(6)
	print 'prefix = {}'.format(raw.encode('hex'))
	challenge = raw_input('Challenge: ')
	temp = sha256(raw + challenge).hexdigest()
	if temp.startswith('25455'):
	return True
	else:
	return False


	if __name__ == "__main__":
	try:
	assert proof_of_shit() == True
	N, delta, gamma = gen_key()

	m = int(FLAG.encode('hex'), 16)
	c = powmod(m, 0x10001, N)

	print introduction
	print 'N = {}'.format(N)
	print 'delta = {}'.format(delta)
	print 'gamma = {}'.format(gamma)
	print 'ciphertext = {}'.format(c)

	except AssertionError:
	print "Take your time and think of the inputs."
	import sys, time, socket, itertools, string
	from hashlib import sha256

	def wait4string(s, p1, p2=None, verbose=True):
	line = ""
	while line.find(p1) == -1 and (p2==None or line.find(p2) == -1):
	try:
	c = s.recv(1)
	except:
	return False
	line += c
	if verbose:
	sys.stdout.write(c)

	return line

	def receive_value(s, prompt, delimiter='\n'):
	wait4string(s, prompt)
	return wait4string(s, delimiter)[:-len(delimiter)]

	def send_value(s, prompt, value):
	wait4string(s, prompt)
	s.send(value + '\n')


	def sqrt_mod_power_of_two(a, k):
	if a % min(2**k, 8) == 1:
	if k == 1:
	return [1]
	elif k == 2:
	return [1, 3]
	elif k == 3:
	return [1, 3, 5, 7]
	else:
	# Small optimization for the case of a == 1.
	if a == 1:
	return [1, 2(k-1) - 1, 2(k-1) + 1, 2**k - 1]
	else:
	roots = []
	for x in sqrt_mod_power_of_two(a, k-1):
	i = 1 if ((x*x - a) >> (k - 1)) % 2 == 1 else 0
	r = x + i*(1 << (k - 2))
	roots.append(r)
	roots.append(2**k - r)
	return list(set(roots))
	return []

	def solve_problem(N, delta, gamma):
	t2 = (delta + 1024)/2
	t1 = 1024-t2
	tt2 = 2**t2
	F.<x> = PolynomialRing(Zmod(N), implementation='NTL')

	for i in xrange(-512, 512):
	diff = gamma//2 + i
	d = (N+diff**2)%tt2
	for r in sqrt_mod_power_of_two(d, t2):
	p0 = r + diff

	# Coppersmith
	pol = x*tt2 + p0
	for root in pol.monic().small_roots(X=2**t1, beta=0.5):
	p = int(root)*tt2 + p0
	q = N // p
	if p<N and q<N and p*q == N:
	return p, q
	return 0, 0

	def proof_of_shit(prefix):
	raw = prefix.decode('hex')
	for i in itertools.product(string.letters+string.digits, repeat=4):
	challenge = ''.join(i)
	temp = sha256(raw + challenge).hexdigest()
	if temp.startswith('25455'):
	return challenge

	def get_problem():
	s = socket.socket(socket.AF_INET, socket.SOCK_STREAM)
	s.connect(("206.189.92.209", 54321))

	prefix = receive_value(s, 'prefix = ')
	send_value(s, 'Challenge: ', proof_of_shit(prefix))

	N = int(receive_value(s, 'N = '))
	delta = int(receive_value(s, 'delta = '))
	gamma = int(receive_value(s, 'gamma = '))
	ciphertext = int(receive_value(s, 'ciphertext = '))

	s.close()

	return N, delta, gamma, ciphertext


	sample_problems = [
	(
	15371749866237646115508350356898072838537706952391263995555938638047512678091547244203379619608626117145212393724653366844752912720621272630141104163458987208064224796167760681043609656284983064426906662893810537320759009783797365080443517944804822707110263161312712740531410411367077103880944521615766398260374415077209037087676578198874509696761864256422299034723840926476366300225520343114927960534284655773996239468008535568776610233953412608042280531797807629722936969010048012255071342744012000262917695278464764342270298361144557893988456450145602415009910229045627863895652984430726880017939957843077135659981,
	564,
	-226299809893849590679441637878369498170874625024638560035914727717118,
	11802632707469573162754173541723445984727582220532965265187609906624038778440270519007571058513140673836179915789232852062150201090926597762810016612939361857580886357121011036542374138868580118230073003496642061470679118663117958022026286699914114637244392685482016550549362473841731417155449455351004539276253989018353281271041423374747038709963100599328059487602428824624557579487442597571103992082843021211283772250686916208840355682507963995060485746870359907102129092007862324533411821101867166147674696760187305327376572128510450857755389172556570031706299891092461249816759961779896520947976331742402773075971
	),
	(
	27571714022630446692205953100246158492104343818129988455758841100800625908329333049812739488534462547281844187880398858752988120705023176776864297511150663619838138626463727122379270088400616428090232830742536890594530487104023780828515169390630286507171033349382225851792980779029965551410119688014838349603230898762802400667244753623403321601517381122132390779455117662264884559525989873640369124355635142220605076029195039341204090577775284758044852508497431261501801774855305788831726565284052375319823081318241303764980093775693900244699784207847658928057210652673501693218497434631625025906040696515446860476313,
	756,
	-1653388744922225434552735986983871360024,
	5638442668480888261640815459781493637271722451633604058526896568348240873974558692467763006225556555199628842538772844043373056249640522719865568364801926391725178640151594865198391904566873806087272052870989078290742545776876474857803824726823211561499369207875202657008341950317589422211493894328981517532660461327247474364787809590589769887989664336482960709851897616673604569569320051687427587493177756239065743745105737456246338933101315533661411929907477377965609507224875416678635297515237594695926117719526744022861218005930819335477380455720839871924821520965155085348952181664215868632028643750071764326129
	)
	]

	# N, delta, gamma, ciphertext = sample_problems[0]
	N, delta, gamma, ciphertext = get_problem()

	p, q = solve_problem(N, delta, gamma)
	if p*q == N:
	d = int(inverse_mod(0x10001, (p-1)*(q-1)))
	m = pow(ciphertext, d, N)

	print ('%x'%m).decode('hex')