# chinese-lazy-theorem-1 (crypto) by joshuazhu17
### Description:```crypto/chinese-lazy-theorem-1joshuazhu17343 solves / 238 points
I heard about this cool theorem called the Chinese Remainder Theorem, but, uh... I'm feeling kinda tired right now.
nc lac.tf 31110```
With the challenge we get a netcat port and a python script. When we execute it and play with it a little bit we get:```1066229023620728201926353841050481690154018395028946037021408022290578286162737405625180437233616854970947095755809150883478502079769638690158323093023354710400792794453506822497021858150371734813592890041673243083813302444860941423466758138490583292186222475219483259176878900821324679812165425564213639620467To quote Pete Bancini, "I'm tired."I'll answer one modulus question, that's it.What do you want?1: Ask for a modulus2: Guess my number3: Exit>> 1Type your modulus here: 133739
What do you want?1: Ask for a modulus2: Guess my number3: Exit>> 2Type your guess here: 1337nope```But since we got the file let's have a look at that.
### Source Code:```#!/usr/local/bin/python3
from Crypto.Util.number import getPrimefrom Crypto.Random.random import randint
p = getPrime(512)q = getPrime(512)n = p*q
target = randint(1, n)
used_oracle = False
print(p)print(q)
print("To quote Pete Bancini, \"I'm tired.\"")print("I'll answer one modulus question, that's it.")while True:    print("What do you want?")    print("1: Ask for a modulus")    print("2: Guess my number")    print("3: Exit")    response = input(">> ")
    if response == "1":        if used_oracle:            print("too lazy")            print()        else:            modulus = input("Type your modulus here: ")            modulus = int(modulus)            if modulus <= 0:                print("something positive pls")                print()            else:                used_oracle = True                print(target%modulus)                print()    elif response == "2":        guess = input("Type your guess here: ")        if int(guess) == target:            with open("flag.txt", "r") as f:                print(f.readline())        else:            print("nope")        exit()    else:        print("bye")        exit()```### Solution:
Looking at it, we see that we have to "guess" the value of `target`. What's interesting, is the option `1` to ask for a modulus.In here, `target` is taken modulo with a number provided by us. Hm, how could we abuse this? Since there is no limitation on the size of our input, we could just provide a number greater or equal to `n` in order to get the "raw" value of `target`. So I just input greater and greater numbers and provided them until I got the flag. A more straightforward way would be to just calculate `n` (since `p` and `q` are given) and input that when asked for a modulus.
So when doing it the straightforward way (multiplying `p` and `q`) we get:```1169623482739382813927905437889026531817501903255837917726614207366061551010434743785266391472831586306450579783954619897663920489046534954859241460695276310334414584883007998613268591963140340928046989003177641426135528191415874389755871175625934213238820818120457667415120042840085818931354798581616683528767To quote Pete Bancini, "I'm tired."I'll answer one modulus question, that's it.What do you want?1: Ask for a modulus2: Guess my number3: Exit>> 1Type your modulus here: 12087373978843536914040287602561953939451674949179759347730736549019049231170157768569328369107444330691725545518320209031846453984017148910662254869641513006744424068690521645422735644312533898033296068510816407072865440080501135805242696682931522007819351064880293642751220326601043296682405404821972063322174063724978047396135929485186362790358896901226652583957312367503438123862469090425241739676164891467168167839384819409765189952353243587861284441817803194570956544645351518001806580718960626401449618669594528889167406989242285558372108154322655190397590870018115173284415791174610567654677419932046886488999
What do you want?1: Ask for a modulus2: Guess my number3: Exit>> 2Type your guess here: 74063724978047396135929485186362790358896901226652583957312367503438123862469090425241739676164891467168167839384819409765189952353243587861284441817803194570956544645351518001806580718960626401449618669594528889167406989242285558372108154322655190397590870018115173284415791174610567654677419932046886488999lactf{too_lazy_to_bound_the_modulus}```Was a quick and fun challenge, thanks!