之前感觉自己数学知识掌握不够，在这种全英式的学习上比较麻烦，刚好最近学了有关的理论知识，可以重新拿这个作为实践了

正文内容多为照搬百度机翻的基础上根据学的知识做了修改，用来看题足矣

CryptoHack简介

这些介绍性挑战旨在引导完成解决挑战和提交flag的过程。

Finding Flags

flag通常采用crypto{y0ur_f1rst_fl4g}格式。

有手就行。

Great Snakes

运行附加的Python脚本，输出flag。

附件：

#!/usr/bin/env python3

import sys
# import this

if sys.version_info.major == 2:
    print("You are running Python 2, which is no longer supported. Please update to Python 3.")

ords = [81, 64, 75, 66, 70, 93, 73, 72, 1, 92, 109, 2, 84, 109, 66, 75, 70, 90, 2, 92, 79]

print("Here is your flag:")
print("".join(chr(o ^ 0x32) for o in ords))
#Here is your flag:
#crypto{z3n_0f_pyth0n}

遍历计算ords数组中的数和0x32异或计算然后转ASCII码，得到flag。

Network Attacks

一些挑战是动态的，需要您通过网络与服务器交互。这允许您对试图通信的人进行中间人攻击，或直接攻击易受攻击的服务。为了保持一致，我们的交互式服务器总是发送和接收JSON对象。
Python使用telnetlib模块使这种网络通信变得容易。方便的是，它是Python标准库的一部分，所以现在让我们使用它。

字典为{"text": 'xxxxxxxxxxx'}形式，python的一些数据如字典和列表等在网站上会用一种叫json的格式存储。

对于这个挑战，请连接到端口11112上的socket.cryptohack.org。发送带有密钥buy flag的JSON对象。

下面的示例脚本包含了一个解决方案的开头。

import telnetlib
import json

HOST = "socket.cryptohack.org"
PORT = 11112

tn = telnetlib.Telnet(HOST, PORT)

def readline():
    return tn.read_until(b"\n")

def json_recv():
    line = readline()
    return json.loads(line.decode())

def json_send(hsh):
    request = json.dumps(hsh).encode()
    tn.write(request)

print(readline())
print(readline())
print(readline())
print(readline())

request = {"buy": "clothes"}
json_send(request)

response = json_recv()
print(response)

'''
b'What would you like to buy?\n'
b"I only speak JSON, I hope that's ok.\n"
b'\n'
{'error': 'Sorry! All we have to sell are flags.'}
'''

上面的示例脚本实现了和服务器的交互，不过本题里面我们需要创建一个buy flag的json对象，我们可以把clothes改为flag：

import telnetlib
import json

HOST = "socket.cryptohack.org"
PORT = 11112

tn = telnetlib.Telnet(HOST, PORT)

def readline():
    return tn.read_until(b"\n")

def json_recv():
    line = readline()
    return json.loads(line.decode())

def json_send(hsh):
    request = json.dumps(hsh).encode()
    tn.write(request)

print(readline())
print(readline())
print(readline())
print(readline())

request = {"buy": "flag"}
json_send(request)

response = json_recv()
print(response)

'''
b"Welcome to netcat's flag shop!\n"
b'What would you like to buy?\n'
b"I only speak JSON, I hope that's ok.\n"
b'\n'
{'flag': 'crypto{sh0pp1ng_f0r_fl4g5}'}
'''

简单加密

ASCII

使用下面的整数数组，将数字转换为相应的ASCII字符以获得flag。

1	[99, 114, 121, 112, 116, 111, 123, 65, 83, 67, 73, 73, 95, 112, 114, 49, 110, 116, 52, 98, 108, 51, 125]

在Python中，chr()函数可用于将ASCII数转换为字符（ord()函数则相反）。

写脚本：

1 2	num=[99, 114, 121, 112, 116, 111, 123, 65, 83, 67, 73, 73, 95, 112, 114, 49, 110, 116, 52, 98, 108, 51, 125] print("".join(chr(i)for i in num))

Hex

十六进制可用于表示ASCII字符串。首先，根据ASCII表将每个字母转换为序数（如前面的挑战）。然后将十进制数转换为十六进制数。这些数字可以组合在一起，形成一个长的十六进制字符串。
下面包含一个编码为十六进制字符串的flag。将其解码回字节以获取flag。

1	63727970746f7b596f755f77696c6c5f62655f776f726b696e675f776974685f6865785f737472696e67735f615f6c6f747d

在Python中，bytes.fromhex()函数可用于将十六进制转换为字节。

脚本：

1 2	hex='63727970746f7b596f755f77696c6c5f62655f776f726b696e675f776974685f6865785f737472696e67735f615f6c6f747d' print(bytes.fromhex(hex))

Base64

正文：

另一种常见的编码方案是Base64，取以下十六进制字符串，将其解码为字节，然后将其编码为Base64。

1	72bca9b68fc16ac7beeb8f849dca1d8a783e8acf9679bf9269f7bf

在Python中，使用import base64导入base64模块后，可以使用base64.b64encode()函数。记住，在挑战描述中，首先解码十六进制。

脚本：

import base64

hex='72bca9b68fc16ac7beeb8f849dca1d8a783e8acf9679bf9269f7bf'
print(base64.b64encode(bytes.fromhex(hex)))

先解码成字节然后编码。

Bytes and Big Integers

如何将信息转换为数字，以便应用数学运算？
最常见的方法是获取消息的ASCII码，将它们转换为十六进制，然后进行连接。这可以解释为十六进制数字，也可以用十进制数字表示。
举例说明：
message: HELLO
ascii bytes: [72, 69, 76, 76, 79]
hex bytes: [0x48, 0x45, 0x4c, 0x4c, 0x4f]
base-16: 0x48454c4c4f
base-10: 310400273487

以上可以用Python的PyCryptodome库使用bytes_to_long()和long_to_bytes()来实现，用from Crypto.Util.number import *导入。

将以下整数转换回消息：

1	11515195063862318899931685488813747395775516287289682636499965282714637259206269

写脚本：

from Crypto.Util.number import *

num=11515195063862318899931685488813747395775516287289682636499965282714637259206269
print(long_to_bytes(num))#b'crypto{3nc0d1n6_4ll_7h3_w4y_d0wn}'

Encoding Challenge

现在我们已经掌握了将要遇到的各种编码的窍门，让我们来看看如何将其自动化。
你能通过所有100级获得flag吗？
下面所附的13377.py文件是服务器上运行的源代码。pwntools_example.py文件提供了使用极其方便的pwntools库的解决方案的开始。这是我们推荐的。如果您希望使用Python内置的telnetlib，还提供telnetlib_example.py。
连接到nc socket.cryptohack.org 13377

服务器源代码：

from Crypto.Util.number import bytes_to_long, long_to_bytes
from utils import listener # this is cryptohack's server-side module and not part of python
import base64
import codecs
import random

FLAG = "crypto{????????????????????}"
ENCODINGS = [
    "base64",
    "hex",
    "rot13",
    "bigint",
    "utf-8",
]
with open('/usr/share/dict/words') as f:
    WORDS = [line.strip().replace("'", "") for line in f.readlines()]


class Challenge():
    def __init__(self):
        self.challenge_words = ""
        self.stage = 0

    def create_level(self):
        self.stage += 1
        self.challenge_words = "_".join(random.choices(WORDS, k=3))
        encoding = random.choice(ENCODINGS)

        if encoding == "base64":
            encoded = base64.b64encode(self.challenge_words.encode()).decode() # wow so encode
        elif encoding == "hex":
            encoded = self.challenge_words.encode().hex()
        elif encoding == "rot13":
            encoded = codecs.encode(self.challenge_words, 'rot_13')
        elif encoding == "bigint":
            encoded = hex(bytes_to_long(self.challenge_words.encode()))
        elif encoding == "utf-8":
            encoded = [ord(b) for b in self.challenge_words]

        return {"type": encoding, "encoded": encoded}

    #
    # This challenge function is called on your input, which must be JSON
    # encoded
    #
    def challenge(self, your_input):
        if self.stage == 0:
            return self.create_level()
        elif self.stage == 100:
            self.exit = True
            return {"flag": FLAG}

        if self.challenge_words == your_input["decoded"]:
            return self.create_level()

        return {"error": "Decoding fail"}

listener.start_server(port=13377)

题目的逻辑很简单，我们连接上服务器之后会返回一个密文，我们需要按照它加密的方式解密出来发送回去，接着会返回第二个密文，我们继续解密……这样我们成功解密持续100轮，服务器就会发送flag。

我们只需要写一个能按照它的解密方法来进行不同种类的解密函数就可以了，然后一直循环解密，我们利用给的telnetlib程序做修改：

import telnetlib
import json
import base64
from Crypto.Util.number import *
import codecs

HOST = "socket.cryptohack.org"
PORT = 13377

tn = telnetlib.Telnet(HOST, PORT)

def readline():
    return tn.read_until(b"\n")

def json_recv():
    line = readline()
    return json.loads(line.decode())

def json_send(hsh):
    request = json.dumps(hsh).encode()
    tn.write(request)

def decode(type,code):
    if type=='base64':
        m=base64.b64decode(code)
        m=str(m,encoding='utf-8')
    elif type=='utf-8':
        m=''.join(chr(i)for i in code)
    elif type=='hex':
        m=bytes.fromhex(code)
        m=str(m,encoding='utf-8')
    elif type=='bigint':
        m=long_to_bytes(int(code,16))
        m=str(m,encoding='utf-8')
    elif type=='rot13':
        m=codecs.decode(code,'rot_13')
    return m
    
i=1
while 1:
    received = json_recv()
    if "flag" in received:
        print(received["flag"])
        break
    text=decode(received["type"],received["encoded"])
    print('round',i,":",text)
    to_send = {"decoded":text}
    json_send(to_send)
    i+=1
'''
round 1 : topics_combined_lancaster
round 2 : balanced_behaviour_performing
round 3 : register_wealth_traditions
round 4 : manufacture_keno_cg
round 5 : jerry_well_dollars
round 6 : puerto_dropped_recommendations
round 7 : compete_finland_vertical
round 8 : adsl_qualifications_kidney
round 9 : kings_finally_cassette
round 10 : occupation_lows_argentina
round 11 : preference_shop_proposed
round 12 : handy_comfortable_fixtures
round 13 : paso_exercises_category
round 14 : indices_sole_reductions
round 15 : tennessee_maiden_classifieds
round 16 : microsoft_make_gps
round 17 : separate_surf_aged
round 18 : scientist_highest_extend
round 19 : uv_dim_european
round 20 : classified_decent_bringing
round 21 : lynn_essentials_kinda
round 22 : dicke_separated_endorsement
round 23 : drive_easily_mirrors
round 24 : hazards_raid_spanking
round 25 : buys_integration_mention
round 26 : unnecessary_observe_prophet
round 27 : lightweight_bi_scored
round 28 : emotions_cents_silence
round 29 : honor_attempting_direct
round 30 : eight_mar_networking
round 31 : jar_luke_payday
round 32 : removing_mining_ft
round 33 : exclude_criminal_sullivan
round 34 : duke_tourist_affiliation
round 35 : rp_preservation_egypt
round 36 : specify_shakespeare_alberta
round 37 : analysts_tongue_searched
round 38 : chemicals_unsubscribe_existence
round 39 : nh_morris_warehouse
round 40 : an_turn_impressive
round 41 : jose_category_boost
round 42 : navy_package_sb
round 43 : tourism_pharmaceutical_british
round 44 : patients_specs_ty
round 45 : structural_intimate_infants
round 46 : possibilities_associates_bahamas
round 47 : groups_sudan_essex
round 48 : gratuit_hostels_mile
round 49 : added_duck_vs
round 50 : conversation_blvd_virginia
round 51 : cables_repair_nc
round 52 : grounds_href_ideas
round 53 : agreements_bargains_latex
round 54 : white_readers_darkness
round 55 : wyoming_curtis_rights
round 56 : auditor_ian_savings
round 57 : leaving_knee_instances
round 58 : worn_dev_sons
round 59 : business_indexed_struck
round 60 : dept_apparatus_reaction
round 61 : told_bullet_traveling
round 62 : saints_illegal_federation
round 63 : def_summer_aware
round 64 : oregon_native_dealers
round 65 : billion_retention_nutritional
round 66 : ministers_sms_archived
round 67 : lookup_sega_son
round 68 : pest_gentleman_bat
round 69 : assessed_fitted_noise
round 70 : physicians_roads_graphic
round 71 : roller_fruit_charity
round 72 : pour_assure_round
round 73 : mathematical_cannon_wholesale
round 74 : charming_divided_yrs
round 75 : ja_absolutely_him
round 76 : metro_verbal_intensive
round 77 : legendary_maker_telecommunications
round 78 : require_contact_photographer
round 79 : eddie_hay_dating
round 80 : bali_civic_organization
round 81 : classics_changed_vs
round 82 : te_pvc_practitioners
round 83 : crisis_headquarters_eg
round 84 : loose_bicycle_behaviour
round 85 : ascii_reef_rug
round 86 : type_czech_loading
round 87 : def_cleaners_reviewed
round 88 : base_email_floor
round 89 : treatment_connection_cottages
round 90 : pin_currency_rome
round 91 : jay_evaluated_applications
round 92 : render_floor_dayton
round 93 : lou_latitude_skype
round 94 : testament_lexus_necessity
round 95 : disciplines_booty_repairs
round 96 : wider_aim_cos
round 97 : freelance_thumbnails_tall
round 98 : dom_handle_hu
round 99 : early_launches_restricted
round 100 : proper_play_meals
crypto{3nc0d3_d3c0d3_3nc0d3}
'''

XOR

XOR Starter

XOR是一种按位运算符，如果位相同，则返回0，否则返回1。“异或”运算符用 ⊕ 表示，但在大多数编程语言中，使用的是 ^ 符号。

A	B	Output
0	0	0
0	1	1
1	0	1
1	1	0

对于较长的二进制数，我们逐位XOR：0110^1010=1100。我们可以通过首先将整数从十进制转换为二进制来对整数进行异或。我们可以通过首先将每个字符转换为表示Unicode字符的整数来对字符串进行XOR。

给定字符串 label，将每个字符与整数13进行异或运算。将这些整数转换回字符串，并将flag作为crypto｛new_string｝提交。

Python pwntools库有一个方便的xor()函数，可以将不同类型和长度的数据进行xor运算。

写脚本：

1
2
3

str='label'
for i in str:
    print(chr(ord(i)^13),end='')#aloha

XOR Properties

使用XOR运算符解决问题时，我们应该考虑四个主要性质：

交换律：$A\oplus B=B\oplus A$
结合律：$A\oplus (B \oplus C)=(A\oplus B)\oplus C$
恒等式：$A\oplus 0=A$
自逆：$A\oplus A=0$

交换律意味着XOR运算的顺序不重要。结合律意味着可以在没有顺序的情况下执行一系列操作（我们不需要担心括号）。标识为0，因此与0的XOR“不起作用”，最后，与自身的XOR运算返回零。
下面是一系列输出，其中三个key与flag一起进行了异或运算。使用以上性质获得flag。

KEY1 = a6c8b6733c9b22de7bc0253266a3867df55acde8635e19c73313
KEY2 ^ KEY1 = 37dcb292030faa90d07eec17e3b1c6d8daf94c35d4c9191a5e1e
KEY2 ^ KEY3 = c1545756687e7573db23aa1c3452a098b71a7fbf0fddddde5fc1
FLAG ^ KEY1 ^ KEY3 ^ KEY2 = 04ee9855208a2cd59091d04767ae47963170d1660df7f56f5faf

在对这些对象进行XOR之前，请确保将十六进制解码为字节。

写脚本：

from Crypto.Util.number import *

KEY1=int('a6c8b6733c9b22de7bc0253266a3867df55acde8635e19c73313',16)
KEY2=int('37dcb292030faa90d07eec17e3b1c6d8daf94c35d4c9191a5e1e',16)^KEY1
KEY3=int('c1545756687e7573db23aa1c3452a098b71a7fbf0fddddde5fc1',16)^KEY2
print(long_to_bytes(int('04ee9855208a2cd59091d04767ae47963170d1660df7f56f5faf',16)^KEY1^KEY2^KEY3))#b'crypto{x0r_i5_ass0c1at1v3}'

Favourite byte

我用一个字节的XOR隐藏了一些数据，但那个字节是一个秘密，别忘了先从十六进制解码。

1	73626960647f6b206821204f21254f7d694f7624662065622127234f726927756d

写脚本：

from Crypto.Util.number import *

hex='73626960647f6b206821204f21254f7d694f7624662065622127234f726927756d'
str=long_to_bytes(int(hex,16))
for i in range(0,128):
    t=''.join(chr(m^i)for m in str)
    if 'crypto' in t:
        print(t,i)
        break#crypto{0x10_15_my_f4v0ur173_by7e} 16

You either know, XOR you don’t

我用我的密钥加密了flag，你永远猜不到。

记住flag格式。

1	0e0b213f26041e480b26217f27342e175d0e070a3c5b103e2526217f27342e175d0e077e263451150104

写脚本：

from Crypto.Util.number import *

hex='0e0b213f26041e480b26217f27342e175d0e070a3c5b103e2526217f27342e175d0e077e263451150104'
str=long_to_bytes(int(hex,16))
res='crypto{'
print(''.join((chr(str[i]^ord(res[i]))) for i in range(7)))
#myXORke
key='myXORkey'
print(''.join((chr(str[i]^ord(key[i%len(key)]))) for i in range(len(str))))
#crypto{1f_y0u_Kn0w_En0uGH_y0u_Kn0w_1t_4ll}

用flag头猜测key然后进行解密。

Lemur XOR

我用相同的密钥通过XOR隐藏了两个很酷的图像，所以你看不到它们！

这一挑战需要在两个图像的RGB字节之间执行视觉XOR，而不是对文件的所有数据字节执行XOR。

这里我们需要用到pillow模块：

from PIL import Image

im1=Image.open("flag.png")#打开图片
img1=im1.load()#图像像素RGB信息
im2=Image.open("lemur.png")
img2=im2.load()
width,height=im1.size#提取图片的高宽，逐个像素点异或

for i in range(width):
    for j in range(height):
        r1,g1,b1=img1[i,j]
        r2,g2,b2=img2[i,j]
        img1[i,j]=(r1^r2,g1^g2,b1^b2)

im1.show()#显示图片

注意这里的load()函数返回值类似于坐标或者矩阵样式，我们需要使用坐标[x,y]对其进行索引。

数据格式

密码学涉及处理各种格式的数据：大整数、原始字节、十六进制字符串等等。一些结构化格式已被标准化，以帮助发送和接收加密数据。它有助于识别和操作这些常见的数据格式。

Privacy-Enhanced Mail?

PEM是一种用于发送密钥、证书和其他加密材料的流行格式。它看起来像：

——-BEGIN RSA PUBLIC KEY——-
MIIBCgKC… (一串base64)
——-END RSA PUBLIC KEY——-

它通过一行页眉和页脚包装base64编码的数据，以指示如何解析其中的数据。页眉和页脚中的连字符数量必须正确，否则加密工具将无法识别文件。
我们要从该PEM格式的RSA密钥中提取私钥d作为十进制整数提交。

解决这一挑战有两种主要方法。证书中的数据可以使用openssl命令行工具读取，也可以使用PyCryptodome在Python中读取。我们建议使用PyCryptodome：首先从Crypto.PublicKey导入RSA模块，然后可以使用RSA.importKey()读取密钥数据。

from Crypto.PublicKey import RSA

d=RSA.importKey(open("mail.pem").read()).d
print(d)

CERTainly not

前面的挑战中，PEM只是DER编码ASN.1之上的一个很好的包装。某些情况下可能会直接遇到DER文件；例如，许多Windows实用程序默认情况下更喜欢使用DER文件。然而，其他工具需要PEM格式，并且很难导入DER文件，所以最好知道如何将一种格式转换为另一种格式。
SSL证书是现代网络的重要组成部分，它将加密密钥绑定到组织的详细信息。我们将在TLS类别中详细介绍这些和PKI。这里提供了一个DER编码的x509 RSA证书。找出证书的模数，并以十进制形式给出答案。

from Crypto.PublicKey import RSA

n=RSA.importKey(open("rsa.der",'rb').read()).n
print(n)

由于这里der文件为二进制编译的文件，我们需要使用rb模式来读取二进制文件。

SSH Keys

SSH是一种网络协议，使用密码学在不安全的网络上建立安全通道。SSH使开发人员和系统管理员能够在世界另一端的服务器上运行命令，而不会嗅探密码或窃取数据。因此，它对网络的安全至关重要。

让我们假设Bruce想作为他的用户帐户bschneier连接到他的服务器bruces-server。他在笔记本电脑上运行ssh bschneier@bruces-server，他的SSH客户端在SSH守护进程监听的端口22上打开与服务器的连接。首先，将要使用的密码是一致的，然后使用Diffie-Hellman密钥交换建立用于加密连接的会话密钥。然后，服务器发送一个用Bruce的公钥加密的随机挑战消息。Bruce使用他的私钥来解密挑战，并将随机挑战消息的散列发送回去，证明他拥有正确的私钥，因此他向服务器认证自己为bschneier。现在，服务器为Bruce提供了运行命令的shell。
SSH私钥以PEM格式存储，并存储在Bruce的笔记本电脑/home/bschneier/.ssh/id_rsa上。但是，SSH公钥使用不同的格式：

ssh-rsa AAAAB3NzaC1yc2EAAAADAQABAAABgQCtPLqba+GFvDHdFVs1Vvdk56cKqqw5cdomlu034666UsoFIqkig8H5kNsNefSpaR/iU7G0ZKCiWRRuAbTsuHN+Cz526XhQvzgKTBkTGYXdF/WdG/6/umou3Z0+wJvTZgvEmeEclvitBrPZkzhAK1M5ypgNR4p8scJplTgSSb84Ckqul/Dj/Sh+fwo6sU3S3j92qc27BVGChpQiGwjjut4CkHauzQA/gKCBIiLyzoFcLEHhjOBOEErnvrRPWCIAJhALkwV2rUbD4g1IWa7QI2q3nB0nlnjPnjjwaR7TpH4gy2NSIYNDdC1PZ8reBaFnGTXgzhQ2t0ROBNb+ZDgH8Fy+KTG+gEakpu20bRqB86NN6frDLOkZ9x3w32tJtqqrJTALy4Oi3MW0XPO61UBT133VNqAbNYGE2gx+mXBVOezbsY46C/V2fmxBJJKY/SFNs8wOVOHKwqRH0GI5VsG1YZClX3fqk8GDJYREaoyoL3HKQt1Ue/ZW7TlPRYzAoIB62C0= bschneier@facts

这种格式使这些公钥更容易作为行添加到服务器上的文件/home/bshneier/.ssh/authorized_keys中。将公钥添加到此文件允许使用相应的私钥在服务器上进行身份验证。
ssh keygen命令用于生成这些公私密钥对。

现在从Bruce的SSH公钥中提取模数n作为十进制整数。

from Crypto.PublicKey import RSA

n=RSA.import_key(open("bruce_rsa.pub").read()).n
print(n)

数学运算

本课程的目的是帮助在数学方面打下坚实的基础，所有公钥密码都是建立在数学基础上的。在模块运算的核心，我们正在使用熟悉的运算，如加法、乘法和求幂。
然而，与越来越大的整数不同，模运算反而“绕圈”并返回到零。

Greatest Common Divisor

最大公因数（GCD）是能将两个正整数$(a,b)$整除的最大数。
对于$a=12，b=8$，我们可以计算$a:\{1,2,3,4,6,12\}$的因数和$b:\{1,2,4,8\}$的因数。比较这两者，我们发现$gcd(a,b)=4$。
现在假设我们取$a=11，b=17$。$a$和$b$都是素数。由于素数只有自身和1作为除数，因此$gcd(a,b)=1$。
我们说，对于任意两个整数$a，b$，如果$gcd(a,b)=1$，那么$a$和$b$是互素整数。
如果$a$和$b$是素数，它们也是互素的。如果$a$是素数并且$b<a$，那么$a$和$b$是互素的。

想想$a$是素数和$b>a$的情况，为什么它们不一定是互质的？

$b$可能是$a$这个素数的倍数，他们并不互质。

有很多工具可以计算两个整数的GCD，但对于这个任务，建议查找欧几里得算法。
现在计算$a=66528，b=52920$的$gcd(a,b)$

使用辗转相除法：

def gcd(a,b):
    if a<b:#我们让a为除数，b为被除数，让a＞b
        a,b=b,a
    while b!=0:
        c=a%b
        a,b=b,c#上一个式子的被除数是下一个的除数，让余数作为下一个式子的被除数，如果余数为0直接输出a
    return a

print(gcd(66528,52920))

Extended GCD

设a和b为正整数。
扩展欧几里得算法是找到整数$u，v$的有效方法：$au+bv=gcd(a,b)$

学习解密RSA时，我们将需要这个算法来计算公共指数的模逆。

使用两个素数$p=26513，q=32321$，求出整数$u，v$，使得
$pu+qv=gcd(p,q)$
输入$u,v$中较低的数字作为flag。

写脚本，这里我们可以用第三方库帮助我们运算，也可以自己写：

def gcdext(a,b):
    if a == 0 and b == 0:
        return None
    else:
        s1,t1,s2,t2=1,0,0,1
        while b:
            q,r=a//b,a%b
            a,b=b,r
            s1,t1,s2,t2=s2,t2,s1-q*s2,t1-q*t2
        if a>0:
            return (a,s1,t1)
        else:
            return (-a,-s1,-t1)

print(gcdext(26513,32321))#(1, 10245, -8404)

1
2
3

import gmpy2

print(gmpy2.gcdext(26513,32321))#(mpz(1), mpz(10245), mpz(-8404))

Modular Arithmetic 1

我们说如果$a≡b (\bmod m)$，则两个整数模m相等。

另一种说法是，当我们将整数a除以m时，余数是b。这告诉你，如果m整除a（可以写成$m|a$），那么$a≡0 (\bmod m)$。
计算以下整数，解是两个整数中较小的一个：

1 2	11 ≡ x mod 6 8146798528947 ≡ y mod 17

1	print(min(11%6,8146798528947%17))#4

Modular Arithmetic 2

假设我们选择了一个模p，我们将把自己限制在p是素数的情况下。模p的整数定义一个字段，表示为$F_p$。

如果模数不是质数，则模n的整数集合定义了一个环。

有限域$F_p$是整数$\{0,1，…，p-1\}$的集合，并且在加法和乘法下，集合中的每个元素$a$都有一个逆元素$b$，使得$a+b=0$，$a\cdot b=1$。

注意，加法和乘法的单位元不同，这是因为当与运算符一起操作时，恒等式不应该有变化：$a+0=a$,$1×a=a$。

假设我们选取$p=17$，计算$317 \bmod 17$，现在做同样的操作，但使用$517 \bmod 17$。
预计$716 \bmod 17$会得到什么？试着计算一下。
这个有趣的事实被称为费马小定理。
现在取素数$p=65537$。计算$273246787654^{65536} \bmod 65537$。
需要计算器吗？

根据费马小定理$a^{p-1}\equiv 1 (\bmod p)$，题目答案为1。

Modular Inverting

我们可以在有限域$F_p$内工作，添加和相乘元素，并总是获得该域的另一个元素。
对于域中的所有元素$g$，存在唯一的整数$d$，使得$gd≡1 \bmod p$，$d$是$g$的乘法逆元。
示例：$7×8=56≡1 \bmod 11$
求$3d≡1 \bmod 13$

1
2
3

import gmpy2

print(gmpy2.invert(3,13))#9

Quadratic Residues

我们已经研究过模运算中的乘法和除法，但将平方根取模成整数意味着什么？
对于下面的讨论，让我们对$p=29$进行模运算。我们可以取整数$a=11$并计算$a^2\bmod 29=5 $。
当$a=11，a^2=5$时，我们说$5$的平方根是$11$。

但现在让我们考虑一下18的平方根。从上面，我们知道我们需要找到一些整数a，使得$a^2=18$
方法是从$a=1$开始并循环到$a=p-1$。在本次讨论中，$p$不太大，我们可以很快得到。
试着编写代码，会发现对于所有的$a∈F_p^*$，永远找不到$a^2＝18$的$a$。
我们看到的是，对于$F_p^*$的元素，并不是每个元素都有平方根。事实上，我们会发现大约一半元素没有平方根。

如果存在这样的$a，a^2＝x \bmod p$，我们说整数$x$是二次剩余。如果没有这样的解，则整数是二次非剩余。

换句话说，当可以将$x$的平方根取模于整数$p$时，$x$是二次剩余。
在下面的列表中，有两个非二次剩余和一个二次剩余。
找到二次剩余，然后计算其平方根。在两个可能的根中，提交较小的根作为flag。

如果$a^2=x$，则$(-a)^2=x$。因此，如果$x$是某个有限域中的二次剩余，则a总是有两个解。

1 2	p = 29 ints = [14, 6, 11]

for j in range(1,29):#设j寻找29的二次剩余
    list=[]
    for i in range(1,29):
        if i**2%29==j:#选出二次剩余j的平方根j
            list.append(i)
    if len(list)!=0:
        print(j,list)
'''
1 [1, 28]
4 [2, 27]
5 [11, 18]
6 [8, 21]#6是二次剩余，得到其两个根
7 [6, 23]
9 [3, 26]
13 [10, 19]
16 [4, 25]
20 [7, 22]
22 [14, 15]
23 [9, 20]
24 [13, 16]
25 [5, 24]
28 [12, 17]
'''

Legendre Symbol

在前面求平方根的例子中，当$p=29$时，即使是最简单的遍历计算平方根的方法也足够快，但随着$p$变大，这种方法变得非常不合理。
幸运的是，多亏了勒让德符号，我们有了一种通过一次计算来检查整数是否为二次剩余的方法。在下文中，我们将假设我们对素数$p$进行模运算。
在看勒让德的符号之前，让我们先绕一圈看看二次（非）剩余的一个有趣的性质。

二次剩余×二次剩余=二次剩余
二次剩余×二次非剩余=二次剩余
二次非剩余×二次非剩余=二次剩余

为了方便记忆，用+1替换“二次剩余”，用-1替换“二次非剩余”，三个结果相同。

勒让德符号提供了一种有效的方法来确定整数是否是模奇素数$p$的二次剩余。
勒让德符号：$(\frac ap)≡a^{\frac{p-1}2} \bmod p$，有以下性质：

如果a是二次剩余且$a\not \equiv 0 \bmod p$，有$(\frac ap)=1$
如果a是二次非剩余模$p$，有$(\frac ap)=-1$
如果$a≡0 \bmod p$，则$(\frac ap)=0$

这意味着给定任何整数a，计算$pow(a,\frac{p-1}2,p)$就足以确定$a$是否为二次剩余。
现在，给定以下1024位素数和10个整数，找到二次剩余，然后计算其平方根；平方根是flag。在两个可能的根中，提交较大的根作为答案。

所以勒让德的符号告诉我们哪个整数是二次剩余，但我们如何找到平方根？所提供的素数遵循$p\equiv3 \bmod 4$，这使得我们可以很容易地计算平方根，想一想费马小定理。

$a^p\equiv a \bmod p$，用$b^2=a$求出其平方根。

根据$p\equiv3 \bmod 4$知道$\frac{p+1}4$是整数，我们可以设$c^2=a$，如果$b^2=a$，$c^2=c^pc=c^{p+1}$，有$b^2=c^{p+1}$

整理得到$b=a^{\frac{p+1}4}$

1
2

p = 101524035174539890485408575671085261788758965189060164484385690801466167356667036677932998889725476582421738788500738738503134356158197247473850273565349249573867251280253564698939768700489401960767007716413932851838937641880157263936985954881657889497583485535527613578457628399173971810541670838543309159139
ints = [25081841204695904475894082974192007718642931811040324543182130088804239047149283334700530600468528298920930150221871666297194395061462592781551275161695411167049544771049769000895119729307495913024360169904315078028798025169985966732789207320203861858234048872508633514498384390497048416012928086480326832803, 45471765180330439060504647480621449634904192839383897212809808339619841633826534856109999027962620381874878086991125854247108359699799913776917227058286090426484548349388138935504299609200377899052716663351188664096302672712078508601311725863678223874157861163196340391008634419348573975841578359355931590555, 17364140182001694956465593533200623738590196990236340894554145562517924989208719245429557645254953527658049246737589538280332010533027062477684237933221198639948938784244510469138826808187365678322547992099715229218615475923754896960363138890331502811292427146595752813297603265829581292183917027983351121325, 14388109104985808487337749876058284426747816961971581447380608277949200244660381570568531129775053684256071819837294436069133592772543582735985855506250660938574234958754211349215293281645205354069970790155237033436065434572020652955666855773232074749487007626050323967496732359278657193580493324467258802863, 4379499308310772821004090447650785095356643590411706358119239166662089428685562719233435615196994728767593223519226235062647670077854687031681041462632566890129595506430188602238753450337691441293042716909901692570971955078924699306873191983953501093343423248482960643055943413031768521782634679536276233318, 85256449776780591202928235662805033201684571648990042997557084658000067050672130152734911919581661523957075992761662315262685030115255938352540032297113615687815976039390537716707854569980516690246592112936796917504034711418465442893323439490171095447109457355598873230115172636184525449905022174536414781771, 50576597458517451578431293746926099486388286246142012476814190030935689430726042810458344828563913001012415702876199708216875020997112089693759638454900092580746638631062117961876611545851157613835724635005253792316142379239047654392970415343694657580353333217547079551304961116837545648785312490665576832987, 96868738830341112368094632337476840272563704408573054404213766500407517251810212494515862176356916912627172280446141202661640191237336568731069327906100896178776245311689857997012187599140875912026589672629935267844696976980890380730867520071059572350667913710344648377601017758188404474812654737363275994871, 4881261656846638800623549662943393234361061827128610120046315649707078244180313661063004390750821317096754282796876479695558644108492317407662131441224257537276274962372021273583478509416358764706098471849536036184924640593888902859441388472856822541452041181244337124767666161645827145408781917658423571721, 18237936726367556664171427575475596460727369368246286138804284742124256700367133250078608537129877968287885457417957868580553371999414227484737603688992620953200143688061024092623556471053006464123205133894607923801371986027458274343737860395496260538663183193877539815179246700525865152165600985105257601565]

p = 101524035174539890485408575671085261788758965189060164484385690801466167356667036677932998889725476582421738788500738738503134356158197247473850273565349249573867251280253564698939768700489401960767007716413932851838937641880157263936985954881657889497583485535527613578457628399173971810541670838543309159139
ints = [25081841204695904475894082974192007718642931811040324543182130088804239047149283334700530600468528298920930150221871666297194395061462592781551275161695411167049544771049769000895119729307495913024360169904315078028798025169985966732789207320203861858234048872508633514498384390497048416012928086480326832803, 45471765180330439060504647480621449634904192839383897212809808339619841633826534856109999027962620381874878086991125854247108359699799913776917227058286090426484548349388138935504299609200377899052716663351188664096302672712078508601311725863678223874157861163196340391008634419348573975841578359355931590555, 17364140182001694956465593533200623738590196990236340894554145562517924989208719245429557645254953527658049246737589538280332010533027062477684237933221198639948938784244510469138826808187365678322547992099715229218615475923754896960363138890331502811292427146595752813297603265829581292183917027983351121325, 14388109104985808487337749876058284426747816961971581447380608277949200244660381570568531129775053684256071819837294436069133592772543582735985855506250660938574234958754211349215293281645205354069970790155237033436065434572020652955666855773232074749487007626050323967496732359278657193580493324467258802863, 4379499308310772821004090447650785095356643590411706358119239166662089428685562719233435615196994728767593223519226235062647670077854687031681041462632566890129595506430188602238753450337691441293042716909901692570971955078924699306873191983953501093343423248482960643055943413031768521782634679536276233318, 85256449776780591202928235662805033201684571648990042997557084658000067050672130152734911919581661523957075992761662315262685030115255938352540032297113615687815976039390537716707854569980516690246592112936796917504034711418465442893323439490171095447109457355598873230115172636184525449905022174536414781771, 50576597458517451578431293746926099486388286246142012476814190030935689430726042810458344828563913001012415702876199708216875020997112089693759638454900092580746638631062117961876611545851157613835724635005253792316142379239047654392970415343694657580353333217547079551304961116837545648785312490665576832987, 96868738830341112368094632337476840272563704408573054404213766500407517251810212494515862176356916912627172280446141202661640191237336568731069327906100896178776245311689857997012187599140875912026589672629935267844696976980890380730867520071059572350667913710344648377601017758188404474812654737363275994871, 4881261656846638800623549662943393234361061827128610120046315649707078244180313661063004390750821317096754282796876479695558644108492317407662131441224257537276274962372021273583478509416358764706098471849536036184924640593888902859441388472856822541452041181244337124767666161645827145408781917658423571721, 18237936726367556664171427575475596460727369368246286138804284742124256700367133250078608537129877968287885457417957868580553371999414227484737603688992620953200143688061024092623556471053006464123205133894607923801371986027458274343737860395496260538663183193877539815179246700525865152165600985105257601565]

for i in ints:
    if pow(i,(p-1)//2,p)==1 and i%p!=0:
        print(i)#85256449776780591202928235662805033201684571648990042997557084658000067050672130152734911919581661523957075992761662315262685030115255938352540032297113615687815976039390537716707854569980516690246592112936796917504034711418465442893323439490171095447109457355598873230115172636184525449905022174536414781771
res=pow(i,(p+1)//4,p)
print(max(res,p-res))#93291799125366706806545638475797430512104976066103610269938025709952247020061090804870186195285998727680200979853848718589126765742550855954805290253592144209552123062161458584575060939481368210688629862036958857604707468372384278049741369153506182660264876115428251983455344219194133033177700490981696141526

Modular Square Root

在勒让德符号中，我们引入了一种快速方法来确定一个数是否是模素数的平方根。我们可以更进一步：有算法可以有效地计算这些根。实践中最好的一种叫做Tonelli Shanks，它在19世纪由一位意大利人首次描述，1970年代由Daniel Shanks独立发现。
所有不是2的素数都是$p≡1 \bmod 4$或$p≡3 \bmod 4$的形式，因为所有奇数都服从这些同余。正如前面的挑战所暗示的，在$p≡3 \bmod 4$的情况下，计算平方根的一个非常简单的公式可以直接从费马小定理推导出来。这就剩下$p≡1 \bmod 4$的情况，所以需要一个更通用的算法。
在形式为$b^2≡a \bmod p$的同余中，可以使用Tonelli Shanks计算$b$。

Tonelli Shanks不适用于非素模数。求平方根在计算上等同于整数分解，也就是说，这是一个难题。

该算法的主要用例是查找椭圆曲线交点坐标，这里求2048位素数p的模的平方根。给出两个根中较小的一个作为答案。

1
2

a = 8479994658316772151941616510097127087554541274812435112009425778595495359700244470400642403747058566807127814165396640215844192327900454116257979487432016769329970767046735091249898678088061634796559556704959846424131820416048436501387617211770124292793308079214153179977624440438616958575058361193975686620046439877308339989295604537867493683872778843921771307305602776398786978353866231661453376056771972069776398999013769588936194859344941268223184197231368887060609212875507518936172060702209557124430477137421847130682601666968691651447236917018634902407704797328509461854842432015009878011354022108661461024768
p = 30531851861994333252675935111487950694414332763909083514133769861350960895076504687261369815735742549428789138300843082086550059082835141454526618160634109969195486322015775943030060449557090064811940139431735209185996454739163555910726493597222646855506445602953689527405362207926990442391705014604777038685880527537489845359101552442292804398472642356609304810680731556542002301547846635101455995732584071355903010856718680732337369128498655255277003643669031694516851390505923416710601212618443109844041514942401969629158975457079026906304328749039997262960301209158175920051890620947063936347307238412281568760161

使用sagemath进行计算：

①R.<x> = Zmod(module)[]
相当于将$x$作为需要求得的未知数，Zmod()内填入同余运算的模数。

②f=x^3+.....

将同余运算的所有项移到同一边，赋值给函数$f$来表示。

③f.roots()

求解，用列表形式返回所有解。

④f.smallroots(upper)

或者以upper为界限在这个上限内求解根。

这题我们要求解$x^2\equiv a \bmod p$，模数为$p$，我们先把所有项移到一边，用$f$函数表示：$f=x^2-a$

就可以用sagemath进行求解：

a = 8479994658316772151941616510097127087554541274812435112009425778595495359700244470400642403747058566807127814165396640215844192327900454116257979487432016769329970767046735091249898678088061634796559556704959846424131820416048436501387617211770124292793308079214153179977624440438616958575058361193975686620046439877308339989295604537867493683872778843921771307305602776398786978353866231661453376056771972069776398999013769588936194859344941268223184197231368887060609212875507518936172060702209557124430477137421847130682601666968691651447236917018634902407704797328509461854842432015009878011354022108661461024768
p = 30531851861994333252675935111487950694414332763909083514133769861350960895076504687261369815735742549428789138300843082086550059082835141454526618160634109969195486322015775943030060449557090064811940139431735209185996454739163555910726493597222646855506445602953689527405362207926990442391705014604777038685880527537489845359101552442292804398472642356609304810680731556542002301547846635101455995732584071355903010856718680732337369128498655255277003643669031694516851390505923416710601212618443109844041514942401969629158975457079026906304328749039997262960301209158175920051890620947063936347307238412281568760161
R.<x> = Zmod(p)[]
f = x^2-a
rr=f.roots()
#rr=[(28169512554311284614348161812907461395482195258388583125795498809297226147214152907614055638917789190356917578259717792167302913007927989841763977292434488782635964253677743342038748567333074043589267896292373028724763808006697707070301035339291758998923066001985927788808579330075671953036025191791621915640175242425390397212674797332132801882880223506177201168864920484993546017284338829512010922075018689505381642887042980971582058343875078178836965895987271392081926458392283354971823611423820865651283490761548053384731721391637064349021755899877224522161311561209530712702153163501623531290150340903913036821041,1), (2362339307683048638327773298580489298932137505520500388338271052053734747862351779647314176817953359071871560041125289919247146074907151612762640868199621186559522068338032600991311882224016021222672243139362180461232646732465848840425458257930887856583379600967761738596782877851318489355679822813155123045705285112099448146426755110160002515592418850432103641815811071548456284263507805589445073657565381850521367969675699760755310784623577076440037747681760302434924932113640061738777601194622244192758024180853916244427254065441962557282572849162772740798989647948645207349737457445440405057156897508368531939120,1)]
min(rr[0][0],rr[1][0])#2362339307683048638327773298580489298932137505520500388338271052053734747862351779647314176817953359071871560041125289919247146074907151612762640868199621186559522068338032600991311882224016021222672243139362180461232646732465848840425458257930887856583379600967761738596782877851318489355679822813155123045705285112099448146426755110160002515592418850432103641815811071548456284263507805589445073657565381850521367969675699760755310784623577076440037747681760302434924932113640061738777601194622244192758024180853916244427254065441962557282572849162772740798989647948645207349737457445440405057156897508368531939120

做完后发现可以使用sage自带的函数进行计算，计算速度快不少：

from sage.rings.finite_rings.integer_mod import square_root_mod_prime

a = 8479994658316772151941616510097127087554541274812435112009425778595495359700244470400642403747058566807127814165396640215844192327900454116257979487432016769329970767046735091249898678088061634796559556704959846424131820416048436501387617211770124292793308079214153179977624440438616958575058361193975686620046439877308339989295604537867493683872778843921771307305602776398786978353866231661453376056771972069776398999013769588936194859344941268223184197231368887060609212875507518936172060702209557124430477137421847130682601666968691651447236917018634902407704797328509461854842432015009878011354022108661461024768
p = 30531851861994333252675935111487950694414332763909083514133769861350960895076504687261369815735742549428789138300843082086550059082835141454526618160634109969195486322015775943030060449557090064811940139431735209185996454739163555910726493597222646855506445602953689527405362207926990442391705014604777038685880527537489845359101552442292804398472642356609304810680731556542002301547846635101455995732584071355903010856718680732337369128498655255277003643669031694516851390505923416710601212618443109844041514942401969629158975457079026906304328749039997262960301209158175920051890620947063936347307238412281568760161

print(square_root_mod_prime(Mod(a, p), p))

Chinese Remainder Theorem

中国剩余定理给出了一组线性同余方程的唯一解，如果它们的模是互质的。
这意味着，给定一组任意整数$a_i$和成对互素整数$n_i$，使得以下线性同余成立：

注意“成对互质整数”意味着如果我们有一组整数$\{n_1,n_2,…,n_i\}$，则从该组中选择的所有整数对都是互质的：$gcd(n_i,n_j)=1$。

$\begin{cases}x ≡ a_1 \bmod n_1\\\\ x ≡ a_2 \bmod n_2\\\\ ...\\\\ x ≡ a_n \bmod n_n\end{cases}$

有一个唯一的解$x≡a \bmod N$，其中$N=n_1\cdot n_2\cdot …\cdot n_n$中。
在密码学中，我们通常使用中国剩余定理来帮助我们将一个非常大的整数问题简化为一组更简单的问题。
给定以下一组线性同余，求整数$a$，使得$x≡a\bmod 935$

$\begin{cases}x ≡ 2 \bmod 5\\\\ x ≡ 3 \bmod 11\\\\ x ≡ 5 \bmod 17\end{cases}$

$x≡a \bmod p$，我们可以为任意整数$k$写成$x=a+kp$。

import gmpy2

n1=5;n2=11;n3=17
a1=2;a2=3;a3=5
N=n1*n2*n3
N1=N//n1;N2=N//n2;N3=N//n3
x=(N1*gmpy2.invert(N1,n1)*a1+N2*gmpy2.invert(N2,n2)*a2+N3*gmpy2.invert(N3,n3)*a3)%N
print(x)#872

知道中国剩余定理的求解公式即可：$x=\sum^m_{i=1}N_iN_i^{-1}a_i$

Successive Powers

以下整数：588, 665, 216, 113, 642, 4, 836, 114, 851, 492, 819, 237是整数$x$用三位素数$p$取模的连续阶乘结果：

$\begin{cases}t_0x\equiv t_1 \bmod p \\\\t_1x\equiv t_2\bmod p\\\\...\\\\t_{10}x\equiv t_{11}\bmod p \end{cases}$

找到$p$和$x$以获得flag。

根据题目所述，我们能发现：

$\begin{cases}x\equiv t_0^{-1}t_1 \bmod p \\\\x\equiv t_1^{-1}t_2\bmod p\\\\...\\\\x\equiv t_{10}^{-1}t_{11}\bmod p \end{cases}$

遍历即可求得$p$：

import gmpy2

t = [588, 665, 216, 113, 642, 4, 836, 114, 851, 492, 819, 237]
for p in range(max(t)+1,1000):
    try:
        x=[gmpy2.invert(t[i],p)*t[i+1]%p for i in range(0,len(t)-1)]
        if len(set(x))==1:
            print(p,int(x[0]))
    except:
        pass

Adrien’s Signs

Adrien一直在寻找用符号和负号加密他的信息的方法。你能找到恢复flag的方法吗？

题目：

from random import randint

a = 288260533169915
p = 1007621497415251

FLAG = b'crypto{????????????????????}'

def encrypt_flag(flag):
    ciphertext = []
    plaintext = ''.join([bin(i)[2:].zfill(8) for i in flag])
    for b in plaintext:
        e = randint(1, p)
        n = pow(a, e, p)
        if b == '1':
            ciphertext.append(n)
        else:
            n = -n % p
            ciphertext.append(n)
    return ciphertext

print(encrypt_flag(FLAG))
#[67594220461269, 501237540280788, 718316769824518, 296304224247167, 48290626940198, 30829701196032, 521453693392074, 840985324383794, 770420008897119, 745131486581197, 729163531979577, 334563813238599, 289746215495432, 538664937794468, 894085795317163, 983410189487558, 863330928724430, 996272871140947, 352175210511707, 306237700811584, 631393408838583, 589243747914057, 538776819034934, 365364592128161, 454970171810424, 986711310037393, 657756453404881, 388329936724352, 90991447679370, 714742162831112, 62293519842555, 653941126489711, 448552658212336, 970169071154259, 339472870407614, 406225588145372, 205721593331090, 926225022409823, 904451547059845, 789074084078342, 886420071481685, 796827329208633, 433047156347276, 21271315846750, 719248860593631, 534059295222748, 879864647580512, 918055794962142, 635545050939893, 319549343320339, 93008646178282, 926080110625306, 385476640825005, 483740420173050, 866208659796189, 883359067574584, 913405110264883, 898864873510337, 208598541987988, 23412800024088, 911541450703474, 57446699305445, 513296484586451, 180356843554043, 756391301483653, 823695939808936, 452898981558365, 383286682802447, 381394258915860, 385482809649632, 357950424436020, 212891024562585, 906036654538589, 706766032862393, 500658491083279, 134746243085697, 240386541491998, 850341345692155, 826490944132718, 329513332018620, 41046816597282, 396581286424992, 488863267297267, 92023040998362, 529684488438507, 925328511390026, 524897846090435, 413156582909097, 840524616502482, 325719016994120, 402494835113608, 145033960690364, 43932113323388, 683561775499473, 434510534220939, 92584300328516, 763767269974656, 289837041593468, 11468527450938, 628247946152943, 8844724571683, 813851806959975, 72001988637120, 875394575395153, 70667866716476, 75304931994100, 226809172374264, 767059176444181, 45462007920789, 472607315695803, 325973946551448, 64200767729194, 534886246409921, 950408390792175, 492288777130394, 226746605380806, 944479111810431, 776057001143579, 658971626589122, 231918349590349, 699710172246548, 122457405264610, 643115611310737, 999072890586878, 203230862786955, 348112034218733, 240143417330886, 927148962961842, 661569511006072, 190334725550806, 763365444730995, 516228913786395, 846501182194443, 741210200995504, 511935604454925, 687689993302203, 631038090127480, 961606522916414, 138550017953034, 932105540686829, 215285284639233, 772628158955819, 496858298527292, 730971468815108, 896733219370353, 967083685727881, 607660822695530, 650953466617730, 133773994258132, 623283311953090, 436380836970128, 237114930094468, 115451711811481, 674593269112948, 140400921371770, 659335660634071, 536749311958781, 854645598266824, 303305169095255, 91430489108219, 573739385205188, 400604977158702, 728593782212529, 807432219147040, 893541884126828, 183964371201281, 422680633277230, 218817645778789, 313025293025224, 657253930848472, 747562211812373, 83456701182914, 470417289614736, 641146659305859, 468130225316006, 46960547227850, 875638267674897, 662661765336441, 186533085001285, 743250648436106, 451414956181714, 527954145201673, 922589993405001, 242119479617901, 865476357142231, 988987578447349, 430198555146088, 477890180119931, 844464003254807, 503374203275928, 775374254241792, 346653210679737, 789242808338116, 48503976498612, 604300186163323, 475930096252359, 860836853339514, 994513691290102, 591343659366796, 944852018048514, 82396968629164, 152776642436549, 916070996204621, 305574094667054, 981194179562189, 126174175810273, 55636640522694, 44670495393401, 74724541586529, 988608465654705, 870533906709633, 374564052429787, 486493568142979, 469485372072295, 221153171135022, 289713227465073, 952450431038075, 107298466441025, 938262809228861, 253919870663003, 835790485199226, 655456538877798, 595464842927075, 191621819564547]

根据上面学的有关二次剩余的知识即可求解：

from Crypto.Util.number import *

list = [67594220461269, 501237540280788, 718316769824518, 296304224247167, 48290626940198, 30829701196032, 521453693392074, 840985324383794, 770420008897119, 745131486581197, 729163531979577, 334563813238599, 289746215495432, 538664937794468, 894085795317163, 983410189487558, 863330928724430, 996272871140947, 352175210511707, 306237700811584, 631393408838583, 589243747914057, 538776819034934, 365364592128161, 454970171810424, 986711310037393, 657756453404881, 388329936724352, 90991447679370, 714742162831112, 62293519842555, 653941126489711, 448552658212336, 970169071154259, 339472870407614, 406225588145372, 205721593331090, 926225022409823, 904451547059845, 789074084078342, 886420071481685, 796827329208633, 433047156347276, 21271315846750, 719248860593631, 534059295222748, 879864647580512, 918055794962142, 635545050939893, 319549343320339, 93008646178282, 926080110625306, 385476640825005, 483740420173050, 866208659796189, 883359067574584, 913405110264883, 898864873510337, 208598541987988, 23412800024088, 911541450703474, 57446699305445, 513296484586451, 180356843554043, 756391301483653, 823695939808936, 452898981558365, 383286682802447, 381394258915860, 385482809649632, 357950424436020, 212891024562585, 906036654538589, 706766032862393, 500658491083279, 134746243085697, 240386541491998, 850341345692155, 826490944132718, 329513332018620, 41046816597282, 396581286424992, 488863267297267, 92023040998362, 529684488438507, 925328511390026, 524897846090435, 413156582909097, 840524616502482, 325719016994120, 402494835113608, 145033960690364, 43932113323388, 683561775499473, 434510534220939, 92584300328516, 763767269974656, 289837041593468, 11468527450938, 628247946152943, 8844724571683, 813851806959975, 72001988637120, 875394575395153, 70667866716476, 75304931994100, 226809172374264, 767059176444181, 45462007920789, 472607315695803, 325973946551448, 64200767729194, 534886246409921, 950408390792175, 492288777130394, 226746605380806, 944479111810431, 776057001143579, 658971626589122, 231918349590349, 699710172246548, 122457405264610, 643115611310737, 999072890586878, 203230862786955, 348112034218733, 240143417330886, 927148962961842, 661569511006072, 190334725550806, 763365444730995, 516228913786395, 846501182194443, 741210200995504, 511935604454925, 687689993302203, 631038090127480, 961606522916414, 138550017953034, 932105540686829, 215285284639233, 772628158955819, 496858298527292, 730971468815108, 896733219370353, 967083685727881, 607660822695530, 650953466617730, 133773994258132, 623283311953090, 436380836970128, 237114930094468, 115451711811481, 674593269112948, 140400921371770, 659335660634071, 536749311958781, 854645598266824, 303305169095255, 91430489108219, 573739385205188, 400604977158702, 728593782212529, 807432219147040, 893541884126828, 183964371201281, 422680633277230, 218817645778789, 313025293025224, 657253930848472, 747562211812373, 83456701182914, 470417289614736, 641146659305859, 468130225316006, 46960547227850, 875638267674897, 662661765336441, 186533085001285, 743250648436106, 451414956181714, 527954145201673, 922589993405001, 242119479617901, 865476357142231, 988987578447349, 430198555146088, 477890180119931, 844464003254807, 503374203275928, 775374254241792, 346653210679737, 789242808338116, 48503976498612, 604300186163323, 475930096252359, 860836853339514, 994513691290102, 591343659366796, 944852018048514, 82396968629164, 152776642436549, 916070996204621, 305574094667054, 981194179562189, 126174175810273, 55636640522694, 44670495393401, 74724541586529, 988608465654705, 870533906709633, 374564052429787, 486493568142979, 469485372072295, 221153171135022, 289713227465073, 952450431038075, 107298466441025, 938262809228861, 253919870663003, 835790485199226, 655456538877798, 595464842927075, 191621819564547]
a = 288260533169915
p = 1007621497415251

ap=pow(a,(p-1)//2,p)
print(ap)#1，a是p的二次剩余，a的e次方也是二次剩余

num=''
for i in list:#判断i是否是二次剩余，如果是则编码1，不是编码0
    if pow(i,(p-1)//2,p)==1:
        num+='1'
    else:
        num+='0'
print(long_to_bytes(int(num,2)))#b'crypto{p4tterns_1n_re5idu3s}'

Modular Binomials

分解模数：

$N = pq$
$c_1 = (2p + 3q)^{e_1} \bmod N$
$c_2 = (5p + 7q)^{e_2} \bmod N$

N = 14905562257842714057932724129575002825405393502650869767115942606408600343380327866258982402447992564988466588305174271674657844352454543958847568190372446723549627752274442789184236490768272313187410077124234699854724907039770193680822495470532218905083459730998003622926152590597710213127952141056029516116785229504645179830037937222022291571738973603920664929150436463632305664687903244972880062028301085749434688159905768052041207513149370212313943117665914802379158613359049957688563885391972151218676545972118494969247440489763431359679770422939441710783575668679693678435669541781490217731619224470152467768073
e1 = 12886657667389660800780796462970504910193928992888518978200029826975978624718627799215564700096007849924866627154987365059524315097631111242449314835868137
e2 = 12110586673991788415780355139635579057920926864887110308343229256046868242179445444897790171351302575188607117081580121488253540215781625598048021161675697
c1 = 14010729418703228234352465883041270611113735889838753433295478495763409056136734155612156934673988344882629541204985909650433819205298939877837314145082403528055884752079219150739849992921393509593620449489882380176216648401057401569934043087087362272303101549800941212057354903559653373299153430753882035233354304783275982332995766778499425529570008008029401325668301144188970480975565215953953985078281395545902102245755862663621187438677596628109967066418993851632543137353041712721919291521767262678140115188735994447949166616101182806820741928292882642234238450207472914232596747755261325098225968268926580993051
c2 = 14386997138637978860748278986945098648507142864584111124202580365103793165811666987664851210230009375267398957979494066880296418013345006977654742303441030008490816239306394492168516278328851513359596253775965916326353050138738183351643338294802012193721879700283088378587949921991198231956871429805847767716137817313612304833733918657887480468724409753522369325138502059408241232155633806496752350562284794715321835226991147547651155287812485862794935695241612676255374480132722940682140395725089329445356434489384831036205387293760789976615210310436732813848937666608611803196199865435145094486231635966885932646519

推导过程：

$\begin{cases}c_1\equiv (2p+3q)^{e_1}(\bmod N)\\\\ c_2\equiv (5p+7q)^{e_2}(\bmod N)\end{cases}$

二项式展开，包含$pq$的项能被$N$整除，约去：

$\begin{cases}c_1^{e_2}\equiv (2p)^{e_1e_2}+(3q)^{e_1e_2}(\bmod N)\\\\ c_2^{e_1}\equiv (5p)^{e_1e_2}+(7q)^{e_1e_2}(\bmod N)\end{cases}$ $\begin{cases}2^{-e_1e_2}c_1^{e_2}\equiv p^{e_1e_2}+2^{-e_1e_2}(3q)^{e_1e_2}(\bmod N)\\\\ 5^{-e_1e_2}c_2^{e_1}\equiv p^{e_1e_2}+5^{-e_1e_2}(7q)^{e_1e_2}(\bmod N)\end{cases}$ $2^{-e_1e_2}c_1^{e_2}-5^{-e_1e_2}c_2^{e_1}\equiv 2^{-e_1e_2}(3q)^{e_1e_2}-5^{-e_1e_2}(7q)^{e_1e_2}(\bmod N)$ $2^{-e_1e_2}c_1^{e_2}-5^{-e_1e_2}c_2^{e_1}\equiv q^{e_1e_2}(2^{-e_1e_2}3^{e_1e_2}-5^{-e_1e_2}7^{e_1e_2})(\bmod N)$

我们能用已知数据求出左边，左恒等于右，右边和$N$有公共因子$q$，可得$q$：

import gmpy2

n = 14905562257842714057932724129575002825405393502650869767115942606408600343380327866258982402447992564988466588305174271674657844352454543958847568190372446723549627752274442789184236490768272313187410077124234699854724907039770193680822495470532218905083459730998003622926152590597710213127952141056029516116785229504645179830037937222022291571738973603920664929150436463632305664687903244972880062028301085749434688159905768052041207513149370212313943117665914802379158613359049957688563885391972151218676545972118494969247440489763431359679770422939441710783575668679693678435669541781490217731619224470152467768073
e1 = 12886657667389660800780796462970504910193928992888518978200029826975978624718627799215564700096007849924866627154987365059524315097631111242449314835868137
e2 = 12110586673991788415780355139635579057920926864887110308343229256046868242179445444897790171351302575188607117081580121488253540215781625598048021161675697
c1 = 14010729418703228234352465883041270611113735889838753433295478495763409056136734155612156934673988344882629541204985909650433819205298939877837314145082403528055884752079219150739849992921393509593620449489882380176216648401057401569934043087087362272303101549800941212057354903559653373299153430753882035233354304783275982332995766778499425529570008008029401325668301144188970480975565215953953985078281395545902102245755862663621187438677596628109967066418993851632543137353041712721919291521767262678140115188735994447949166616101182806820741928292882642234238450207472914232596747755261325098225968268926580993051
c2 = 14386997138637978860748278986945098648507142864584111124202580365103793165811666987664851210230009375267398957979494066880296418013345006977654742303441030008490816239306394492168516278328851513359596253775965916326353050138738183351643338294802012193721879700283088378587949921991198231956871429805847767716137817313612304833733918657887480468724409753522369325138502059408241232155633806496752350562284794715321835226991147547651155287812485862794935695241612676255374480132722940682140395725089329445356434489384831036205387293760789976615210310436732813848937666608611803196199865435145094486231635966885932646519

q=gmpy2.gcd(n,(gmpy2.invert(pow(2,e1*e2,n),n)*pow(c1,e2,n)-gmpy2.invert(pow(5,e1*e2,n),n)*pow(c2,e1,n))%n)
p=n//q
print(p,q)
#112274000169258486390262064441991200608556376127408952701514962644340921899196091557519382763356534106376906489445103255177593594898966250176773605432765983897105047795619470659157057093771407309168345670541418772427807148039207489900810013783673957984006269120652134007689272484517805398390277308001719431273 
#132760587806365301971479157072031448380135765794466787456948786731168095877956875295282661565488242190731593282663694728914945967253173047324353981530949360031535707374701705328450856944598803228299967009004598984671293494375599408764139743217465012770376728876547958852025425539298410751132782632817947101601

Broken RSA

1
2
3

n = 27772857409875257529415990911214211975844307184430241451899407838750503024323367895540981606586709985980003435082116995888017731426634845808624796292507989171497629109450825818587383112280639037484593490692935998202437639626747133650990603333094513531505209954273004473567193235535061942991750932725808679249964667090723480397916715320876867803719301313440005075056481203859010490836599717523664197112053206745235908610484907715210436413015546671034478367679465233737115549451849810421017181842615880836253875862101545582922437858358265964489786463923280312860843031914516061327752183283528015684588796400861331354873
e = 16
ct = 11303174761894431146735697569489134747234975144162172162401674567273034831391936916397234068346115459134602443963604063679379285919302225719050193590179240191429612072131629779948379821039610415099784351073443218911356328815458050694493726951231241096695626477586428880220528001269746547018741237131741255022371957489462380305100634600499204435763201371188769446054925748151987175656677342779043435047048130599123081581036362712208692748034620245590448762406543804069935873123161582756799517226666835316588896306926659321054276507714414876684738121421124177324568084533020088172040422767194971217814466953837590498718

给了三个值，e是偶数，n测了一下为质数，phi和e不互素，但是e可以不断被2分解，所以可以对已知明文不断求二次方根，直到e被分解完为止，需要用到Tonelli-Shanks算法，直接照搬脚本了：

import gmpy2

n = 27772857409875257529415990911214211975844307184430241451899407838750503024323367895540981606586709985980003435082116995888017731426634845808624796292507989171497629109450825818587383112280639037484593490692935998202437639626747133650990603333094513531505209954273004473567193235535061942991750932725808679249964667090723480397916715320876867803719301313440005075056481203859010490836599717523664197112053206745235908610484907715210436413015546671034478367679465233737115549451849810421017181842615880836253875862101545582922437858358265964489786463923280312860843031914516061327752183283528015684588796400861331354873
e = 16
c = 11303174761894431146735697569489134747234975144162172162401674567273034831391936916397234068346115459134602443963604063679379285919302225719050193590179240191429612072131629779948379821039610415099784351073443218911356328815458050694493726951231241096695626477586428880220528001269746547018741237131741255022371957489462380305100634600499204435763201371188769446054925748151987175656677342779043435047048130599123081581036362712208692748034620245590448762406543804069935873123161582756799517226666835316588896306926659321054276507714414876684738121421124177324568084533020088172040422767194971217814466953837590498718

def legendre(a, p):#勒让德符号
    return pow(a, (p - 1) // 2, p)

def tonelli(n, p):#求n在模p下平方根
    assert legendre(n, p) == 1
    q = p - 1
    s = 0
    while q % 2 == 0:
        q //= 2
        s += 1
    if s == 1:
        return pow(n, (p + 1) // 4, p)
    for z in range(2, p):
        if p - 1 == legendre(z, p):
            break
    c = pow(z, q, p)
    r = pow(n, (q + 1) // 2, p)
    t = pow(n, q, p)
    m = s
    t2 = 0
    while (t - 1) % p != 0:
        t2 = (t * t) % p
        for i in range(1, m):
            if (t2 - 1) % p == 0:
                break
            t2 = (t2 * t2) % p
        b = pow(c, 1 << (m - i - 1), p)
        r = (r * b) % p
        c = (b * b) % p
        t = (t * c) % p
        m = i
    return r

count = 0
while e % 2 == 0:
    e = e // 2
    count += 1
d = gmpy2.invert(1,n-1)
m = pow(c, d, n)
for i in range(count):
    m = tonelli(m, n)
m = -m % n
print(bytes.fromhex(hex(m)[2:]).decode())

格

Vectors

域$F$上的向量空间$V$是由两个二元运算符定义的集合。对于向量$v∈V$和标量$a∈F$，向量加法取两个向量并产生另一个向量：$v+w=z$，对于$v,w,z∈V$，标量乘法取向量和标量并产生向量：$av=w$，对于$v,w∈V，a∈F$。

让我们考虑实数上的二维向量空间。向量$v∈V$可以被视为一对数字：$v=(A,b),a,b∈R$。向量加法的工作原理为$v+w=(a,b)+(c,d)=(a+c,b+d)$，标量乘：$cv=c(a,b)=(ca,cb)$
也可以定义内积（也称为点积），它取两个向量并返回标量。形式上，我们认为这是$v\cdot w=a$，对于$v,w∈V，a∈F$。在我们的二维示例中，内积的工作方式为$v\cdot w=(a,b)\cdot (c,d)=ac+bd$
下面求解flag：给定在实数上定义的三维向量空间，其中$v=(2,6,3),w=(1,0,0),u=(7,7,2)$，计算$3(2v-w)\cdot 2u$：

def v_add(v,w):#向量加法
    a,b,c=v
    d,e,f=w
    x,y,z=a+d,b+e,c+f
    return (x,y,z)

def v_sub(v,w):#向量减法
    a,b,c=v
    d,e,f=w
    x,y,z=a-d,b-e,c-f
    return (x,y,z)

def a_mul(c,v):#标量乘
    x,y,z=v
    return (c*x,c*y,c*z)

def v_mul(v,w):#点积
    a,b,c=v
    d,e,f=w
    return a*d+b*e+c*f

v=(2,6,3)
w=(1,0,0)
u=(7,7,2)
print(v_mul(a_mul(3,v_sub(a_mul(2,v),w)),a_mul(2,u)))

Size and Basis

我们说一组向量$v_1,v_2,…,v_k\in V$线性独立如果方程：
$a_1v_1+a_2v_2+…+a_kv_k=0$
的唯一解为：$a_1=a_2=…=a_k=0$

使其可视化可以想象一个指向某一点的向量。给定一组线性无关向量，返回原点的唯一方法是沿着原始向量移动。任何其他向量的组合都不会让你到达那里。

基是一组线性无关的向量$v_1,v_2,…,v_n∈V$，使得任何向量$w∈V$可以写成：
$w=a_1v_1+a_2v_2+…+a_kv_n$
基中元素的数量也是向量空间的维数。
我们定义向量的大小，表示为$||v||$，使用向量与自身的内积来定义向量大小的平方：$||v||^2=v∙v$
如果对于向量基$v_1,v_2,…,v_n∈V$，任意两个不同向量之间的内积为零：$v_i∙v_j=0,i≠j$
如果一个基是正交的并且对于任意一个向量有：$||v_i||=1$，则它是正交的。
给定向量$v=(4,6,2,5)$，计算其大小：

from gmpy2 import sqrt

def v_mul(v,w):
    a,b,c,d=v
    e,f,g,h=w
    return sqrt(a*e+b*f+c*g+d*h)

v=(4,6,2,5)
print(v_mul(v,v))

Gram Schmidt

在上一个挑战中，我们看到有一种特殊的基叫做正交基。给定基$v_1,v_2,…,v_n\in V$，对于向量空间，我们可以使用Gram-Schmidt算法计算正交基$u_1,u_2,…,u_n∈V$

Gram-Schmidt算法

$u_1=v_1$

在$i=2,3…,n$循环：

计算$μ_{ij}=\frac{v_i\cdot u_j}{||u_j||^2},1≤j<i$

定义$ui=\sum{1≤j<i}vi-μ{ij}u_j$

结束循环。

给定以下基向量：
$v_1= (4,1,3,-1), v_2 = (2,1,-3,4), v_3 = (1,0,-2,7), v_4 = (6, 2, 9, -5)$
使用Gram-Schmidt算法计算正交基，flag是$u_4$的第二个分量到5个有效数字的浮点值。

sage上有关于Gram-Schmidt算法相关函数：

1
2
3

V = matrix(QQ, [[4.0,1.0,3.0,-1.0], [2.0,1.0,-3.0,4.0], [1.0,0.0,-2.0,7.0], [6.0, 2.0, 9.0, -5.0]])
print(V.gram_schmidt())
print(float(V.gram_schmidt()[0][3][1]))

What’s a Lattice?

给定一组线性无关向量$v_1,v_2,…,v_n∈R^m$，格$L$的构成：

$L＝\{a_1v_1+a_2v_2+…+a_kv_k:a_1,a_2,…,a_n∈Z\}$

格$L$的基是生成$L$的任何一组独立向量。基的选择远非唯一。下图展示了一个二维格，其中有两个不同的基向量，由$u_1,u_2$和$v_1,v_2$给出：

使用基，我们可以用基向量的整数倍到达格内的任何点。基向量还定义了基本域：

$F(v_1,…,v_n)＝\{t_1v_1+t_2 v_2+…+t_n v_n:0≤t_i<1\}$

作为二维的例子，基本域是相邻边为$u_1$和$u_2$的平行四边形。
我们可以根据基向量计算基本域的体积。作为一个例子，让我们以基向量$v=(2,5),u=(3,1)$的二维格为例。创建一个矩阵$A$，其行对应于基向量：$A=[[2,5],[3,1]]$。基本域的体积是A的行列式的大小：$Vol(F)=|det(A)|=|2×1-5×3|=|-13|=13$，$det()$为矩阵的行列式值。
现在使用基向量$v_1=(6,2,-3),v_2=(5,1,4),v_3=(2,7,1)$计算基本域的体积。

还是使用sage：

1 2	V = matrix([[6.0,2.0,-3.0], [5.0,1.0,4.0], [2.0,7.0,1.0]]) abs(det(V))#255

Gaussian Reduction

如果仔细观察能发现，格在密码学中随处可见。有时，它们是通过操纵密码系统而出现的，破坏了生成得不够安全的参数。最著名的例子是Coppersmith对RSA密码的攻击。
格也可用于构建密码协议，其安全性基于两个基本的问题：
最短向量问题（SVP）：在格$L$中找到最短的非零向量。换句话说，在$v∈L$中找到非零向量，使得$||v||$最小化。
最接近向量问题（CVP）：给定不在$L$中的向量$w∈R^m$，找到最接近$w$的向量$v∈L$，即找到向量$v∈L$，使得$||v-w||$最小化。
SVP对于一般格来说很难，但对于足够简单的情况，有有效的算法来计算SVP的解或近似值。当格的维数为4或更小时，我们可以在多项式时间内精确计算；对于更高的维度，我们必须满足于一个近似值。
高斯发展了他的算法，在给定任意基的情况下，找到二维格的最优基。此外，算法的输出$v_1$是$L$中最短的非零向量，因此求解SVP。

对于更高的维度，有一种称为LLL算法的基本格简化算法，以Lenstra、Lenstra和Lovász命名。LLL算法在多项式时间内运行。

高斯的算法通过从一个基向量减去另一个基矢量的倍数来大致工作，直到不再可能使它们变小为止。因为这是在二维空间中工作的，所以很容易可视化：

高斯格点约简算法

循环：

如果$||v_2||<||v_1||$，交换$v_1,v_2$的值。

计算$m=[\frac{v_1\cdot v_2}{v_1\cdot v_1}]$

如果$m=0$，返回值$v_1,v_2$

否则，$v_2=v_2-m\cdot v_1$，继续循环。

可以很容易注意到这种算法与欧几里得的GCD算法在“交换”和“减少”步骤上的相似性，并且对浮点进行了舍入，因为在格上，我们可能只使用整数系数作为基向量。
对于flag，取两个向量$v = (846835985, 9834798552), u = (87502093, 123094980)$，通过应用高斯算法，找到最佳基。标志是新基向量的内积。

按照上面的算法写程序即可：

from gmpy2 import sqrt

def v_mul(v,w):
    a,b=v
    c,d=w
    return a*c+b*d

def v_sub(v,w):
    a,b=v
    c,d=w
    x,y=a-c,b-d
    return (x,y)

def a_mul(c,v):
    x,y=v
    return (c*x,c*y)

def size(v):
    a,b=v
    return sqrt(a*a+b*b)

def Gaussian(v,u):
    while 1:
        if size(u)<size(v):
            v,u=u,v
        m=v_mul(v,u)//v_mul(v,v)
        if m==0:
            return v,u
        else:
            u=v_sub(u,a_mul(m,v))

v=(846835985, 9834798552)
u=(87502093, 123094980)
v,u=Gaussian(v,u)
print(v_mul(v,u))

Find the Lattice

正如我们所看到的，格包含可以形成密码系统trapdoor函数的难题。我们还发现，在密码分析中，格可以破坏最初看起来与格无关的密码协议。
这个挑战使用模块化算法来加密flag，但隐藏在协议中的是一个二维网格。这是一个著名的例子，有大量可用资源，但知道如何在系统中发现格往往是打破格的关键。
作为提示，使用上一个挑战的高斯缩减来打破这个挑战：

from Crypto.Util.number import getPrime, inverse, bytes_to_long
import random
import math

FLAG = b'crypto{?????????????????????}'

def gen_key():
    q = getPrime(512)
    upper_bound = int(math.sqrt(q // 2))
    lower_bound = int(math.sqrt(q // 4))
    f = random.randint(2, upper_bound)
    while True:
        g = random.randint(lower_bound, upper_bound)
        if math.gcd(f, g) == 1:
            break
    h = (inverse(f, q)*g) % q
    return (q, h), (f, g)

def encrypt(q, h, m):
    assert m < int(math.sqrt(q // 2))
    r = random.randint(2, int(math.sqrt(q // 2)))
    e = (r*h + m) % q
    return e

def decrypt(q, h, f, g, e):
    a = (f*e) % q
    m = (a*inverse(f, g)) % g
    return m

public, private = gen_key()
q, h = public
f, g = private

m = bytes_to_long(FLAG)
e = encrypt(q, h, m)

print(f'Public key: {(q,h)}')
print(f'Encrypted Flag: {e}')
'''
q=7638232120454925879231554234011842347641017888219021175304217358715878636183252433454896490677496516149889316745664606749499241420160898019203925115292257
h=2163268902194560093843693572170199707501787797497998463462129592239973581462651622978282637513865274199374452805292639586264791317439029535926401109074800
e=5605696495253720664142881956908624307570671858477482119657436163663663844731169035682344974286379049123733356009125671924280312532755241162267269123486523
'''

阅读题目，已知$q,h,e$，想要使用decrypt函数，我们还需要$f,g$，我们发现：

$h\equiv f^{-1}g \bmod q\iff fh\equiv g \bmod q$ $e\equiv rh+m \bmod q$

我们需要构建格，来进行求解，根据上面的同余关系式：$fh-kq=g①$

构造格需要满足一定的条件，我们让向量$(f,g)$在我们要设的格上，根据已知条件我们可以设：$a(c,h)+b(d,q)=(f,g)$

这里有好几个未知数（$a,b,c,d$），由上式我们可以发现：$ah+bq=g$，也就和①式对上了，我们可以得到：

$f(c,h)-k(d,q)=(f,g)$

同时，有：$cf-kd=f$，我们就可以大胆的认定：$c=1,d=0$，格就构造出来了，基向量为$(1,h),(0,q)$：

注意到：

def gen_key():
    q = getPrime(512)
    upper_bound = int(math.sqrt(q // 2))
    lower_bound = int(math.sqrt(q // 4))
    f = random.randint(2, upper_bound)
    g = random.randint(lower_bound, upper_bound)

$f,g$都不超过256位，比起$h$和$q$的512位小了非常非常多，我们可以大胆猜测这个$(f,g)$向量是这个格的最短向量，使用之前的高斯的算法求出$(f,g)$，进而求解得到flag：

from Crypto.Util.number import *
from gmpy2 import sqrt

def v_mul(v,w):
    a,b=v
    c,d=w
    return a*c+b*d

def v_sub(v,w):
    a,b=v
    c,d=w
    x,y=a-c,b-d
    return (x,y)

def a_mul(c,v):
    x,y=v
    return (c*x,c*y)

def size(v):
    a,b=v
    return sqrt(a*a+b*b)

def Gaussian(v,u):
    while 1:
        if size(u)<size(v):
            v,u=u,v
        m=v_mul(v,u)//v_mul(v,v)
        if m==0:
            return v,u
        else:
            u=v_sub(u,a_mul(m,v))

def decrypt(q, h, f, g, e):
    a = (f*e) % q
    m = (a*inverse(f, g)) % g
    return m

q=7638232120454925879231554234011842347641017888219021175304217358715878636183252433454896490677496516149889316745664606749499241420160898019203925115292257
h=2163268902194560093843693572170199707501787797497998463462129592239973581462651622978282637513865274199374452805292639586264791317439029535926401109074800
e=5605696495253720664142881956908624307570671858477482119657436163663663844731169035682344974286379049123733356009125671924280312532755241162267269123486523

v=(1,h)
u=(0,q)
print(Gaussian(v,u))#舍去负值
f,g=(47251817614431369468151088301948722761694622606220578981561236563325808178756, 43997957885147078115851147456370880089696256470389782348293341937915504254589)
print(long_to_bytes(decrypt(q, h, f, g, e)))#b'crypto{Gauss_lattice_attack!}'

CryptoHack学习记录（一）

CryptoHack简介

Finding Flags

Great Snakes

Network Attacks

简单加密

ASCII

Hex

Base64

Bytes and Big Integers

Encoding Challenge

XOR

XOR Starter

XOR Properties

Favourite byte

You either know, XOR you don’t

Lemur XOR

数据格式

Privacy-Enhanced Mail?

CERTainly not

SSH Keys

数学运算

Greatest Common Divisor

Extended GCD

Modular Arithmetic 1

Modular Arithmetic 2

Modular Inverting

Quadratic Residues

Legendre Symbol

Modular Square Root

Chinese Remainder Theorem

Successive Powers

Adrien’s Signs

Modular Binomials

Broken RSA

格

Vectors

Size and Basis

Gram Schmidt

What’s a Lattice?

Gaussian Reduction

Find the Lattice

Backpack Cryptography