Coppersmith归纳

发表于2025-06-09|更新于2026-03-31

|浏览量:

归纳一下Coppersmith

1.Background

我们可以利用LLL算法来求解模多项式问题

比如我们想要求解
这个模多项式方程，这个是困难的，我们可以考虑构造整数上与之同解的方程，使得

我们知道当f(x)的系数比较小的时候，这个模多项式方程有可能变成多项式方程，这就可以考虑使用LLL算法求得约化基

注意到而且同解，沿着这个思路
也是同解的，然后我们把h进行线性组合，寄希望与他们的系数可以相互抵消，使得系数绝对值变小

先考虑

引理Howgrave-Graham

设h(x)是一个有d个单项式的多项式，如果满足那么，可以在整数集上求解

由根据柯西不等式而那么

所以

根据上面这个，我们来构造这个模数没统一，我们不妨固定为m吧，那这样的话，前面构造就得改
于是有构造只需令那怎么找到这样的g呢

我们用的系数向量造格子

寻找满足的向量

不妨令LLL约化得到的b_1为这个向量，那么只需令未完待续，但其实根据前面这个引理，已经能得到很多东西了

文章作者: InfinitePwn

文章链接: https://infinitepwn.github.io/2025/06/09/2025-06-09_Coppersmith%E5%BD%92%E7%BA%B3/

版权声明: 本博客所有文章除特别声明外，均采用 CC BY-NC-SA 4.0 许可协议。转载请注明来源 InfinitePwn's Blog！

相关推荐

哈希长度拓展攻击

哈希长度拓展攻击1.什么是MAC?MAC就是Message AuthenticationCodes，即消息验证码 🔐 MAC的核心作用认证性（Authenticity）：确保消息的发送者是声称的人，即消息确实是由合法的发送者生成。完整性（Integrity）：验证消息在传输过程中是否被篡改或损坏。为了实现这些功能，发送者使用一个秘密密钥和MAC算法生成一个认证标签（MAC值），这个标签随消息一起发送。接收者也拥有同样的密钥，可以用相同算法重新生成MAC值。如果重新计算的值和收到的值一致，就可以确认消息没有被改动。这个标签也叫做tag MAC系统包含以下三个算法 A keygeneration algorithm selects a key from the key space uniformly atrandom. A MAC generation algorithm efficiently returns a tag given the keyand the message. A verifying algorithm efficiently verifies th...

1.marin12345678910111213141516171819202122232425#!/usr/bin/env python3import randomfrom Crypto.Util.number import bytes_to_longfrom secret import secrets, flagdef get_prime(secret): prime = 1 for _ in range(secret): prime = prime << 1 return prime - 1random.shuffle(secrets)m = bytes_to_long(flag)p = get_prime(secrets[0])q = get_prime(secrets[1])n = p * qe = 0x10001c = pow(m, e, n)print(f"n = {n}")print(f"e = {e}")print(f"c = {c}") 注意到假设b大于a，然后我们只需要不断除以2，就可以知道a等于多少

轩辕杯crypto-wp

轩辕杯crypto-wp1.简单编码显然A和B就是二进制的0和1，不过哪个是0，哪个是1不知道用Ctrl+F直接替换，得到两种情况发现A=1,B=0,是可以用ASCII码得到有意义的字符的得到 LJWVCMSONJGXSTSHKUZGERCRGJMWU2DMJ5CFM2SNGJKTETLKJJWE4R2WNBGUOVTIJ5KEE3COPJTXOWTKIUZU4RCBGVHVOZDKJUZEM2SZGJEXQTSHKZUFSMSZGJHDESJUMZMHGMCOKRKXUTT2NBUE2UJFGNCCKM2E 注意到这是base32编码，解码得到 ZmQ2NjMyNGU2bDQ2YjhlODVjM2U2MjJlNGVhMGVhOTBlNzgwZjE3NDA5OWdjM2FjY2IxNGVhY2Y2N2I4fXs0NTUzNzhhMQ%3D%3D 看到后面%，疑似url编码 ZmQ2NjMyNGU2bDQ2YjhlODVjM2U2MjJlNGVhMGVhOTBlNzgwZjE3NDA5OWdjM2FjY2IxNGVhY2Y2N2I4fXs0NTUzNzhhMQ== 看到==，...

苦读密码学引论--hash

HASH函数hash函数就是将映射到的函数，即将任意长度的比特串映射为n-bits 即其中H叫做像，M是原像一个好的hash函数需要满足一下属性 1.抗原像攻击给定H,找到X，使得h(X)=H是困难的 2.抗第二原像攻击（弱抗碰撞）给定X,找到X’使得h(X)=h(X’)是困难的 3.抗碰撞攻击找到任意两个X和X’,满足h(X)=h(X’)是困难的（任何一个第二原像都不存在）为什么抗碰撞性更强？如果一个哈希函数是抗碰撞的，那么它必然也是抗第二原像的。理由：如果攻击者能对一个给定的 x成功进行第二原像攻击（找到 x’ 使得H(x’) = H(x)），那么他实际上就找到了一个碰撞对(x, x’)。所以，抗碰撞失败必然导致抗第二原像失败。反之则不然！一个哈希函数可以是抗第二原像的，但却不抗碰撞。理由：攻击者可能无法为某个特定的、随机的x 找到碰撞伙伴x’（满足抗第二原像），但他可能通过精心构造的方法找到任意一对特殊的消息y 和 y’（y 和 y’都不是那个特定的 x），使得H(y) = H(y’)（即不抗碰撞）。MD5就是一个经典例子：虽然在实际中寻找第二原...

1.eazy_log首先加法 2.AAALLL使用AES加密，需要求出key 1key = md5(str(f.list()).encode()).digest() 也就是求出f的系数而f满足 1f = sample_ternery_poly(Q) 首先定义了一个多项式这里n=450,无法因式分解，但是有450个根 12roots = [i[0] for i in g.roots()]print(len(roots)) 为什么？注意到这里原根的概念、性质及其存在性知乎引理3：如果，那么恰好有 d个根。然后我们从中选出225个根然后构造了一个商环也就是进行模运算，将小于n的单项式不会有变化所以f就是在Q上选取了一个449次的多项式，他的系数是-1,0，1由于是有限域p上的，所以-1就是p-1 所以我们的关键就是恢复f的系数我们已知225个根，假设是r 而我们知道于是有那么那么这就是一个格密码的问题了,注意到这个矩阵是Vandermonde矩阵可以考虑 Direct Primal Attack 考虑嵌入技术那么(f|...

Crypto一、simple_equation定个小目标，希望不久的将来就能彻底搞懂这个推导过程经典钓鱼题，就是那个香蕉苹果的题目 AMI_43_from29to41.pdf 此事于此论文亦有记载注意到三个分式都是齐次的所以可以考虑把关系映射到二维空间首先去分母得到然后根据论文里的（暂时还不知道怎么做到的）可以映射到二维空间的椭圆曲线我们知道这个椭圆曲线上的一个点，然后不断倍乘，直到映射回去的a,b,c是正整数就行了映射关系 12345678910111213141516171819202122232425262728293031ee = EllipticCurve([0, 4*10^2+12*10-3, 0, 32*(10+3), 0])print(ee)print(ee.gens())P = ee(-416,4160) def orig(P,N): x = P[0] y = P[1] a = (8*(N+3)-x+y)/(2*(N+3)*(4-x)) b = (8*(N+3)-x-y)/(2*(N+3)*(4-x)) c = ...