526互联

DASCTF Crypto

发布时间 2023-10-27 17:27:35作者: Kur0n1ko

官方wp

EzRsa ✔

$\quad $ 签到题

$\quad $ 到此为止了QAQ

  1. 二次剩余喵

    1. 完全剩余系定理

      如果用一个与模数互质的数去乘完全剩余系的各数，则得到对于模数的又一个完全剩余系

    2. 二次剩余计数定理

      对于奇素数\(m\)，\(p=\frac{m-1}{2}\)，则\(m\)有\(p\)个不同的二次剩余\(1^2,2^2,3^2...p^2\)，其余为非二次剩余
      若再多，则有同余
      若有重复，则\((x-y)(x+y) \equiv 0(mod \; p)\)，然而\(x+y<p\)

    3. 二次剩余乘积定理

      1. 二次乘非二次N为非二次

        对于\(1^2,2^2,3^2...,p^2\)和\(1^2N,2^2N,3^2N...,p^2N\)，前者

      2. 非二次乘非二次为二次

        对于\(1^2N,2^2N,3^2N...,p^2N\)和\(1^2NM,2^2NM,3^2NM...,p^2NM\)，同上

  2. Legendre与Jacobi喵

  3. sagemath解一元多项式组（gcd）

$\quad $

    PR.<x>=PolynomialRing(Zmod(n))
    g1 = (x + noise1)^e1 - c1
    g2 = (x + noise2)^e2 - c2

    def gcd(g1, g2):
        while g2:
            g1, g2 = g2, g1 % g2
        return g1.monic()
    print(gcd(g1, g2))
    return -gcd(g1, g2)[0]
  1. 关于位运算优先级...

CB curve

$\quad $ 论文题 Huff Curve

$\quad $ 然而好像可以直接推柿子

  1. sagemath groebner_basis 解多元高次方程组
	p=998244353
	R.<x,y> = PolynomialRing(Zmod(p))
	f=[]
	f.append(x*x*y*123456+x+y)
	f.append(y*y*123-x*y)
	ans=Ideal(f).groebner_basis()
	print(ans)

ans