摆烂小子

一、数字签名 二、DSA介绍DSA是用于数字签名的算法，基于模算数和离散对数的复杂度。DSA是Schnorr和ElGamal签名方案的变体。 DSA 算法包含了四种操作：密钥生成、密钥分发、签名、验证 1、密钥生成密钥生成包含两个阶段。第一阶段是算法参数的选择，可以在系统的不同用户之间共享，而第二阶段则为每个用户计算独立的密钥组合。 2、密钥分发签名者需要透过可信任的管道发布公钥 y，并且安全地保护 x 不被其他人知道。 3、签名流程 4、验证签名 三、DSA解密1.已知 k：如果知道了随机密钥 k，那么我们就可以根据 s ≡ (H(m)+xr)k−1modq 计算私钥 x。 这里一般情况下，消息的 hash 值都会给出。 x≡r−1(ks−H(m))modq 2.k 共享如果在两次签名的过程中共享了 k，我们就可以进行攻击。 假设签名的消息为 m1,m2，显然，两者的 r 的值一样，此外 s1≡(H(m1)+xr)k−1modq s2≡(H(m2)+xr)k−1modq 这里我们除了 x 和 k 不知道剩下的均知道，那么 s1k≡H(m1)+xr s2k≡H(m2)+xr 两式相减 ...

RSA因子相近分析：我们假定 n = p * q 如果q和p很相近，一般表示为： 123p = getPrime(512)q = gmpy2.next_prime(p)n = p * q 对于这种形式，应该怎么去分析呢？ 首先，第一种方法，可以通过yafu分解，yafu分解适用于p，q相近或相差很大时。 直接使用yafu工具分解即可。 除此之外，还有什么方法能求出p和q呢？ 没错，就是爆破~~~~ 这里讲以下爆破流程： 12345678910111213def factor(n): factor_list = [] a,f = iroot(n,2) while(True): a += 1 try: b,f = iroot(a*a - n, 2) except: pass if f: # b*b == a*a - n return a-b，a+b 爆破原理： a首先好说，a是n的整数平方根，这很好理解，但是b的产生是什么鬼？其中还有个令人费解的式 ...

常用sagemath函数（代数系统篇）1.同余运算1R.<x> = Zmod(module)[] 其中，x作为求解的未知数，module表示同余的模数。 12f = x^3 + ... //将所有式移到f右边f.roots() 例题： 需要求解 n ≡ p ^3 + a ∗ p ^ 2 + b ∗ p (mod n) 那么在sage中写 123R.<p> = Zmod(moudle)f = p^3 + a*p^2 + b*p - n^2 f.roots() 那么p的所有满足该同余式的解就会返回出来 2.有限域2.1 P元有限域有限域 p7 （所有模7的完全剩余类） 1k1=GF(7) 操作有限域上的元素 123a=k1(5)print(a,a^6,a^-1)#5 1 3 求解x ** 5 ≡ 2(mod7) 12print(k1(2).nth_root(5))# 4

首先回顾整数的rsa： ​ 那么，当n是多项式的时候呢？ ​ 有如下推导： 那么显然RSA对于整数的体制可以适用于有限域上的多项式。 解密步骤：对N进行多项式分解，得到多项式p和多项式q，求出phi( p(n) )，之后类似于整数rsa求出d后求出m。 注意: 有限域上的多项式求欧拉函数时，φ(p(x)) ！= x-1 回到欧拉函数定义本身，欧拉函数是小于或等于n的正整数中与n的数的数目。 欧拉函数phi(n)表示小于n的所有与n互质的数的个数，多项式的phi(P(y))则类似，表示不高于P(y)幂级的环内所有多项式中，与P(y)无公因式（非1）的其他多项式的个数。 这里补充一下 有限域GF（p）的知识： 有限域的元素个数是一个素数的幂p ** n，n为正整数，一般记为GF(p ** n)，我们最为关注的只有两种情况：n=1即GF(p)；p为2即GF(2 ** n)。 GF(p)的空间是模p的完全剩余类Zp:{0,1,⋯,p−1} 因此这里，对于p(x)，φ(p(x)) = p ** n - 1 (这里p表示有限域的模数，n表示有限域多项 ...

One Time Pad （一次性密码本）什么是 One Time Pad先来仔细看看什么是 One Time Pad 。 通俗的说，就是存在一个密钥字符串，长度与明文和密文一样，逐位将明文的每一位和密钥的对应位作混淆处理（可能移位，也可能异或以及相加取余等等）。 安全性使用凯撒密文进行加密的时候，我们把信息的每一个字母都按照字母表移动相同的位数。移位数量可以取1到26的任意一个数。比如，我们想加密的信息是 ALICE ，这样其实总的密文的可能性也没有多少种，所以可以很容易用暴力搜索的形式找到信息。 但是使用 One Time Pad 的时候，每一个字母移动的位数是不同的，每一个字母的取值就有26种可能，这样可能生成的密文种类就是26的五次方，有一千多万种可能。这几个移动的位数组成的字符串，就是本次加密的秘钥，长度是跟密文一致的，或者说，它就是一个 One Time Pad 。 可以看到 One Time Pad 是无条件安全的。 局限性One Time Pad 虽然是最强的加密方法，但是也有自己的局限性。 使用 One Time Pad 有两个最佳实践。第一，一个 One Time ...

MT19937预测首先介绍该模块的用法：主要用于预测随机数 getrandbits（k） 用法： 12345678910111213141516>>> import random>>> from mt19937predictor import MT19937Predictor>>> predictor = MT19937Predictor()>>> for _ in range(624):... x = random.getrandbits(32)... predictor.setrandbits(x, 32)>>> random.getrandbits(32) == predictor.getrandbits(32)True>>> random.random() == predictor.random()True>>> a = list(range(100))>>> b = list(range(100))>>&g ...

Shamir秘密共享协议简述Shamir密钥分享算法最早在1970年基于Lagrange插值和矢量方法提出的，基本思想是分发着通过秘密多项式，将秘密s分解为n个秘密，分发给持有者，其中任意不少于t个秘密均能恢复密文，而任意少于t个秘密均无法得到密文的任何信息。 算法思路 实现代码： 加密： 1234567891011121314a = getPrime(256)b = getPrime(256)c = getPrime(256)d = bytes_to_long(flag)n = getStrongPrime(2048)def poly(x): return (a * x ** 3 + b * x ** 2 + c * x + d) % nfor _ in range(4): x = getRandomNBitInteger(256) print(f'({x}, {poly(x)})')print(n) 解密： 12345678910111213141516171819202122232425262 ...

椭圆曲线：椭圆曲线加密算法，简称ECC，是基于椭圆曲线数学理论实现的一种非对称加密算法。相比RSA，ECC优势是可以使用更短的密钥，来实现与RSA相当或更高的安全，RSA加密算法也是一种非对称加密算法，在公开密钥加密和电子商业中RSA被广泛使用。据研究，160位ECC加密安全性相当于1024位RSA加密，210位ECC加密安全性相当于2048位RSA加密（有待考证）。 椭圆曲线方程： 椭圆曲线Ep ( a , b ) p为质数，x , y ∈ [ 0 , p − 1 ] ​ y ** 2 = x ** 3 + ax + b (mod p) 表示在p有限域GF(p)上的椭圆曲线方程。 其中，要求曲线是非奇异的（处处可导），有4 a**3 + 27 b * *2 ≠ 0 加法运算：过曲线上的两点A、B画一条直线，找到直线与椭圆曲线的交点，交点关于x轴对称位置的点，定义为A+B，即为加法。如下图所示：A + B = C 二倍运算上述方法无法解释A + A，即两点重合的情况，因此在这种情况下，将椭圆曲线在A点的切线，与椭圆曲线的交点，交点关于x轴对称位置的点，定 ...

一.Paillier加密介绍Paillier加密系统，是1999年Paillier发明的概率公钥加密系统。基于复合剩余类的困难问题。该加密算法是一种同态加密，满足加法和乘法同态。 1 秘钥生成 2 加密 3.解密 例题[DASCTF 2020 四月春季赛] not_RSA题目： 1234567891011121314151617from Crypto.Util.number import getPrime as getprime ,long_to_bytes,bytes_to_long,inversefrom secret import flag,p,qfrom sympy import isprime,nextprimeimport randomm=bytes_to_long(flag)n=p*qg=n+1r=random.randint(1,n)c=(pow(g,m,n*n)*pow(r,n,n*n))%(n*n)print "c=%d"%(c)print "n=%d"%(n)c=2908891105471150925221561523101 ...

对称加密AES加密思路： ​ 根据分组进行填充  待加密的明文以16字节分组进行加密，如果数据字节长度不是16的倍数，最后的一组则需要在有效数据后面进行填充，使得数据长度变为16字节，AES填充方式分为NoPadding、PKCS5（PKCS7）、ISO10126、Zeros。  NoPadding：不填充，那就只能加密长度为16倍数的数据，一般不使用  Zeros：补0，如果原数据长度恰好是16的倍数，也要补16个0  ISO10126：最后一个字节是填充的字节数（包括最后一字节），其他全部填随机数 加密方法： 加密方式分为五种：电码本模式（Electronic Codebook Book (ECB)）、密码分组链接模式（Cipher Block Chaining (CBC)）、计算器模式（Counter (CTR)）、密码反馈模式（Cipher FeedBack (CFB)）、输出反馈模式（Output FeedBack (OFB)）。实际应用比较多的是ECB和CBC。 ECB模式(Electronic Code Book Mode)ECB模式是最早采用和最简单的模式，它将加密的 ...