在讲解的题目之前你需要了解两个概念一个是裴蜀定理，一个是扩展欧几里得,和辗转相除法思想
裴蜀定理
如果a,b全是不为0的整数，则有整数x,y使ax+by=gcd(a,b)=gcd(b,a%b)
推论
1.如果a,b互质那么可以得到当且仅当存在整数x,y，使得ax+by=1
2.如果a,b不全为0，并且ax*by=c有解，那么c一定是gcd(a,b)的整数倍
3.a,b两项可以广为多项
4.如果在保证a,b,c,都不变的情况下，x,y也是多解的
推论4证明
前提得到了特解的x,y的前提下，求出通解
应为x,y符合
ax+by=gcd(a,b)
令x=x+kb, y=y-ka
那么我们就可得到
a*(x+kb)+b * (y-ka)
=a*x+b *y=gcd(a,b)
论证成功
辗转相除法
辗转相除法的流程如下
gcd(a,b)\\ 1.=gcd(b,a\%b) \;令a\%b为r1 \; 下面同理 \\ 2.=gcd(r1,b\% r1)\\ 3.=gcd(r2,r1\%r2)\\ 一直到\\ 4.gcd(r_n,0)时结束\\ 此时的r_n就是最大公因数
尝试理解下面的过程
当a=120,b=170是求出一组x,y使ax+by=gcd(a,b)成立
gcd(220,170)=10,过程如下：
1.gcd(220,170)\\ 2 .gcd(170,50)\\ 3.gcd(50,20)\\ 4.gcd(20,10)\\ 5.gcd(10,0)\\ 最终得到公因数为10
然后接下来就是求解x,y，我们知道知道从上往下求是不行的，那么就反过来重下往上求，因为从下往上我们有多了一个关系就是上下之间可以直接进行数字的替换。
一步一步看，主要是看得到的余数部分的来源\\ 10=50 \% 20 =50-2*20\\ 10=50-2*(170 \%50)=50-2*(170-3*50) \\10=7*50-2*170\\ 10=7*(220\%170)-2*170=7*(220-170)-2*170\\ 10=7*220-9*170 \\10=7*220+(-9)*170
这样我们就得到了一组x,y.
扩展欧几里得算法
其实这个是为了扩展欧几里得算法就是一个代码没有额外的定义，其目的就是为了解出任意符合裴蜀定理的ab，都可以让其直接输出一组特解x,y.因此他需要将之前我们编写的解题过程更加的规范和代码化
根据之前的编写过程我们发现，对于a,b求出x,y他可以分为两部分1部是从上往下求出公因数，另有部分是利用求出公因数进行反推出x,y。
第一部分：
我们利用gcd()一直推，只有当最后的b结果是0时候，我们才会得到公因数a
第二部分：
还是以220，170为例子
我们得到公因数10的时候
在最后一步可以得到
对于过程5 gcd(10,0)
10*1+0 * 0=10 此时x=1,y=0
过程4 gcd(20,10)
10*1+0 * (20-2*10)=10
20 * 0 +10 * 1 此时x=0,y=1
过程3 gcd(50,20)
20 * 0 +（50-2*20） * 1=10
50*1+( – 2) * 20 =10 此时 x=1,y=-2
过程2 gcd(170,50)
50 * 1 – 2 * (170-3*50)=10
(- 2) * 170+50*7 =10 此时 x=-2 ,y=7
过程1 gcd(220,170)
-2 * 170 +（220-170）* 7=10
7*220-9 * 170 =10 此时 x=7,y=-9
通过这个过程我们不难发现上一层的y1变成了下一层的x2,而下一层的 y2=a2-a2//b2*b2(此时的ab都是当前层的)
关于y2=a2-a2//b2*b2原式为y=a%b你可以理解为y等于a减去a//b乘于b，应为式整除所以剩下的就是余数。
即
x=y
y=a-a//b*b
根据这两个步骤进行编写代码解题代码吧，此外解出来之后可以想一下如何gcd！=1时你的脚本还通用吗
题目
from Crypto.Util.number import *
flag = b'******'
m1 = bytes_to_long(flag[:len(flag)//2])
m2 = bytes_to_long(flag[len(flag)//2:])
assert 18608629446895353521310408885845687520013234781800558*m1-14258810472138345414555137649316815272478951117940067*m2 == 1
from campus import solve
from Crypto.Util.number import *
a=32966910484103083075640153874030504338744721993701
b=64656557295323368947703375019596814279122133838868
def 扩展欧几里得(a,b):
if b==0:
return 1,0,a
else:
x,y,g=扩展欧几里得(b,a%b)
return y,x-(a//b)*y,g
solve=扩展欧几里得(a,b)
x=abs(solve[0])
y=abs(solve[1])
print(a)
print(b)
while(1):
x += b
y += a
flag1=long_to_bytes(x)
print(x)
flag2=long_to_bytes(y)
if b'flag' in long_to_bytes(x):
print(flag1+flag2)
breakflag{6cd6ac0a-1dd8-4a49-9120-9387b00b5bd5}斐波那契数列-AES
from Crypto.Cipher import AES
from Crypto.Util.Padding import pad, unpad
from hashlib import md5
from Crypto.Util.number import*
from Crypto.Cipher import AES
from Crypto.Util.Padding import unpad
from hashlib import md5
iv = bytes.fromhex('a40052319cc54396bd995810e9bff841')
final_cipher = bytes.fromhex("d2e8f59adb48d744e28d760afd11c7d8a7954770baca9c773a7078629db659b82b2f92fd7c5dcd684e7a164bf813bd6affe6e726b48a658dd14356c1fe7227d7")
key2=1779979416004714189
key2 = key2.to_bytes(16, 'big')
key1=2427893228399975082453
key1 = key1.to_bytes(16, 'big')
cipher2 = AES.new(key2, AES.MODE_ECB)
padded_ciphertext = cipher2.decrypt(final_cipher)
ciphertext = unpad(padded_ciphertext, 16)
print(ciphertext.hex())
cipher1 = AES.new(key1, AES.MODE_CBC, iv)
flag = cipher1.decrypt(ciphertext)
flag = unpad(flag, 16)
print(flag)flag{68d83fb4-48ba-444a-9ae4-c152a26f1b55}杨辉三角-RSA
from math import gcd
import hashlib
phi = 209007847911249849150381994932558950560
a = []
for i in range(65):
a.append([1] * (i + 1))
for j in range(1, i):
a[i][j] = a[i - 1][j - 1] + a[i - 1][j]
ans = []
for i in range(65):
for j in range(i + 1):
e = a[i][j]
if 1 < e < phi and gcd(e, phi) == 1:
ans.append(e)
print(ans)
print("数量:", len(ans))
flag ="_".join(map(str, ans))
print(flag)
flag="flag{"+hashlib.md5(flag.encode()).hexdigest()+"}"
print(flag)flag{d220e446f2ca6231fc9443646e220dfd}
