# **Crypto CTF 2020**  ## Amsterdam  ### Category : Easy, Points : 55### Flag : CCTF{With_Re3p3ct_for_Sch4lkwijk_dec3nt_Encoding!}Challenge :  amsterdam.py```#!/usr/bin/env python3
from Crypto.Util.number import *from functools import reduceimport operatorfrom secret import flag, n, k
def comb(n, k):	if k > n :		return 0	k = min(k, n - k)	u = reduce(operator.mul, range(n, n - k, -1), 1)	d = reduce(operator.mul, range(1, k + 1), 1)	return u // d 
def encrypt(msg, n, k):	msg = bytes_to_long(msg.encode('utf-8'))	if msg >= comb(n, k):		return -1	m = ['1'] + ['0' for i in range(n - 1)]	for i in range(1, n + 1):		if msg >= comb(n - i, k):			m[i-1]= '1'			msg -= comb(n - i, k)			k -= 1	m = int(''.join(m), 2)	i, z = 0, [0 for i in range(n - 1)]	c = 0	while (m > 0):		if m % 4 == 1:			c += 3 ** i 			m -= 1		elif m % 4 == 3:			c += 2 * 3 ** i			m += 1		m //= 2		i += 1	return c
enc = encrypt(flag, n, k)print('enc =', enc)```output.txt  ```enc = 5550332817876280162274999855997378479609235817133438293571677699650886802393479724923012712512679874728166741238894341948016359931375508700911359897203801700186950730629587624939700035031277025534500760060328480444149259318830785583493```  
**Analysis :**  Function comb() gives the value of <sup>n</sup>C<sub>k</sub>.  To generate encrypted text, first of all a variable **m** is generated using message(flag) with bits set 1 at special places and a special least significant bit and then this **m** is converted to **enc** using some basic arithmetic operations.  So, basically we have to first find ***m*** from the given ***enc*** value and then make use of the positions of bit **1** in ***m*** to proceed way back to flag.  
**Solution :**  A simple function to find m from enc is:  ```def find_m(c):	i = 0	m = 0	while c > 0:		if c % 3 == 1:			m += 2 ** i			c -= 1		elif c % 3 == 2:			m += (fc(c-2)-1)*(2 ** i)			break		c //= 3		i += 1	return m```and our m is:```>>> m = 13037931070082386429043329808978789360911287214189289770230708339088698578551447560972351036453899271623903109387482345515668380476074788749548946464>>> b = bin(m)[2:]>>> b'1000001010000011110111100000110010110010000000001110111100111010111110100110100000111010111000101100000010111010010011000011010001111101000001101010111110000001000000011000001000110010101000000111111111101101111100000000111101001100001110000110101010101110000100111100100001000101100001011111101001010101010000011010101001001000011010100010000011101011100000110110111101110010011000010111010010111000110110011101001000000110001000000010100000011000000011000010101111001011111111000010000100000'>>> len(b)493```  In binary form, number of bits in m is 493 and this is the value for our **n**.  Let's look at lsb of m which is **0**. Since this is 0, we can say our message after all reductions should follow: 
> msg < comb(0, k)    #some k, will find it later. If msg > comb(0,k) then lsb would have been 1.
Since comb(0, k) = 0 if k is positive or 1 if k = 0, we have  
> msg < 1
Also msg gets reduced by ***msg -= comb(n - i, k) iff msg >= comb(n-i, k)***, so from this we have  
> msg >= 0    #i.e. msg can never be negative
Combining both we get that at last(after all reductions) **msg** will be 0. So we can represent msg as a sum of these combatorials.  Now the question arises, which combatorials to combine ??  Here comes the role of bit positions '1'. Whenever **m** gets reduced by comb(n-i, k), m[i] becomes '1' and k reduces by 1. So whenever we encounter a bit 1 at index 'i' from last, we can write ***m += comb(i,some k)*** and this k incerases by 1 for next value. The positions at which bit '1' appears are (from backwards and excluding last one) :  ```[5, 10, 15, 16, 17, 18, 19, 20, 21, 22, 24, 27, 28, 29, 30, 32, 34, 39, 40, 48, 49, 56, 58, 66, 70, 71, 78, 81, 83, 84, 85, 88, 89, 91, 92, 96, 97, 98, 100, 103, 105, 106, 107, 109, 114, 115, 118, 121, 122, 123, 125, 126, 127, 128, 130, 131, 133, 134, 140, 141, 142, 144, 146, 147, 148, 154, 158, 160, 162, 163, 168, 171, 174, 176, 178, 180, 181, 187, 189, 191, 193, 195, 198, 200, 201, 202, 203, 204, 205, 207, 212, 213, 215, 219, 224, 227, 228, 229, 230, 233, 238, 239, 240, 242, 244, 246, 248, 250, 251, 256, 257, 258, 263, 264, 267, 269, 270, 271, 272, 281, 282, 283, 284, 285, 287, 288, 290, 291, 292, 293, 294, 295, 296, 297, 298, 299, 306, 308, 310, 313, 314, 318, 324, 325, 333, 340, 341, 342, 343, 344, 346, 348, 350, 351, 357, 359, 360, 361, 362, 363, 367, 369, 370, 375, 376, 379, 382, 384, 385, 386, 388, 395, 396, 398, 402, 403, 404, 406, 408, 409, 410, 416, 418, 419, 422, 424, 425, 426, 427, 428, 430, 432, 433, 434, 437, 438, 439, 440, 442, 443, 444, 454, 457, 458, 460, 463, 464, 470, 471, 472, 473, 475, 476, 477, 478, 484, 486]```Using all this knowledge we can represent msg as:  
*msg = comb(5,k) + comb(10,k+1) + comb(15,k+2)+ ... + comb(484,k+215) + comb(486,k+216)*  
All now left is to find the initial k.  From the lsb knowledge of **m**, comb(0,k) is 0 if k is positive which means if at last k>=1,  **msg (which is 0) < comb(0,k) = 0**, <--CONTRADICTION  So at last k becomes 0, which means k in the first term of msg i.e. comb(5,k) would be 1, as after it it will decrease by 1 and finally become 0 to satisfy our lsb condition. 
Full solution is avaliable at [ams_soln.py](https://github.com/ketanch/ctf-writeups/blob/master/Crypto%20CTF%202020/ams_sol.py)
## Three Ravens ### Category : Medium, Points : 90### Flag : CCTF{tH3_thr3E_r4V3n5_ThRe3_cR0w5}Challenge :  three_ravens.py```#!/usr/bin/python
from Crypto.Util.number import *from flag import flag
def keygen(nbit):	while True:		p, q, r = [getPrime(nbit) for _ in range(3)]		if isPrime(p + q + r):			pubkey = (p * q * r, p + q + r)			privkey = (p, q, r)			return pubkey, privkey
def encrypt(msg, pubkey):	enc = pow(bytes_to_long(msg.encode('utf-8')), 0x10001, pubkey[0] * pubkey[1])	return enc
nbit = 512pubkey, _ = keygen(nbit)print('pubkey =', pubkey)
enc = encrypt(flag, pubkey)print('enc =', enc)```output.txt:```pubkey = (1118073551150541760383506765868334289095849217207383428775992128374826037924363098550311115755885268424829560194236035782255428423619054826556807583363177501160213010458887123857150164238253637312857212126083296001975671629067724687807682085295986049189947830021121209617616433866087257702543240938795900959368763108186758449391390546819577861156371516299606594152091361928029030465815445679749601118940372981318726596366101388122993777320367839724909505255914071, 31678428119854378475039974072165136708037257624045332601158556362844808093636775192373992510841508137996049429030654845564354209680913299308777477807442821)enc = 8218052282226011897229703907763521214054254785275511886476861328067117492183790700782505297513098158712472588720489709882417825444704582655690684754154241671286925464578318013917918101067812646322286246947457171618728341255012035871158497984838460855373774074443992317662217415756100649174050915168424995132578902663081333332801110559150194633626102240977726402690504746072115659275869737559251377608054255462124427296423897051386235407536790844019875359350402011464166599355173568372087784974017638074052120442860329810932290582796092736141970287892079554841717950791910180281001178448060567492540466675577782909214```
**Analysis :**  Instead of 2 primes, 3 primes are used and we are provided the sum and product of these primes as public key.  Definition of public modulus **N** is also different and here it is product (pqr) * (p+q+r).  **ASSUMPTION :** I have assumed in my solution that p+q+r > m (message)  We cannot find p,q,r but we can do some tricks to reduce the modulus from **N** to a smaller value whose totient can be found easily and make use of the fact (p+q+r) is Prime.   
**Solution :**  
*N = (p x q x r) x (p+q+r)*  *enc = m<sup>65537</sup> mod N*  
As p+q+r is a factor of N, we can reduce above expression to:  
*enc = m<sup>65537</sup> mod (p+q+r)*  
As p+q+r is also prime ( given in question ), its totient is simply p+q+r-1 :  
*phi = p+q+r-1*  
Now we can compute flag easily:  ```from Crypto.Util.number import *from gmpy2 import invertn = pubkey[1]      #new modulusenc = enc % nphi = n-1e = 65537d = invert(e,phi)flag = long_to_bytes(pow(enc,d,n)).decode()print(flag)```  Instead of using (p+q+r) as modulus, we could have also used pqr, but then the totient would be (p-1) x (q-1) x (r-1), which we do not know.