RSA加解密专题 - 预言机相关攻击
在前面几章中，我们已经介绍了RSA加解密的基本原理和一些相关攻击方法。在本章中，我们将继续深入探讨RSA加解密中的预言机相关攻击。这些攻击利用了预言机（Oracle）的功能来推断出明文或私钥，从而威胁到RSA的安全性。 选择明密文相关攻击 😆这种攻击适用于 oracle（预言机）攻击场景，一般输入明文，返回密文，并且输入的明文中不能包含 flag 还有输入密文，返回明文，并且返回的明文中不能包含flag。 首先，我们选择明文攻击，模数一定是和偶数互质的，所以我们直接选择加密 $2$， $4$， $8$，然后可以知道： \begin{align*} c_1 \equiv 2^e \mod n \\ c_2 \equiv 4^e \mod n \\ c_3 \equiv 8^e \mod n \end{align*}由于我们知道自己输入的明文，所以我们可以知道 $c_1$、$c_2$、$c_3$ 之间的关系： \begin{align*} c_{2}^{2} \equiv c_{4} \mod n \\ c_{2}^{3} \equiv c_{8} \mod n \end{alig...
RSA加解密专题 - Coppersmith 相关攻击二
上一章我们介绍了 Coppersmith 相关攻击的基本原理和实现方法，帮助大家了解了如何利用 Coppersmith 方法来攻击 RSA 加密算法。接下来，我们将继续深入探讨 Coppersmith 相关攻击的应用。 欢迎来到《密码学核心算法实战》的 Coppersmith 相关攻击二专题！这里没有纸上谈兵的理论空谈（真的不画大饼😉），只有一把把能直接撬动数据安全的精密齿轮⚙️。 $d_q$ 的低位泄露攻击 🙃这种情况多见于破损pem文件，或者某些特定的实现中，攻击者可能会获得 $d_q$ 的部分低位信息。我们可以利用这些泄露的低位信息来恢复完整的 $d_q$，进而推导出私钥。 和前一篇文章中的私钥低位泄露一样，我们认识到低位，可以理解成原来的方程在取模时的值，然后我们就可以求解另外的参数的低位，最后通过 Coppersmith 方法求解高位。 $d_q$ 的低位泄露攻击例题$d_q$ 的低位泄露攻击例题下载 ''' 破损私钥以及密文 -----BEGIN RSA PRIVATE KEY----- MIICXgIBAAKBgQDXFSUGqpzsBe...
密码学算法 - BSGS 算法二
上一章我们介绍了 BSGS（Baby-Step Giant-Step）算法的基本原理和实现方法，帮助大家快速求解离散对数问题。接下来，我们将继续深入探讨 BSGS 算法的另一种应用。除了在离散对数问题中，BSGS 算法也可以用于求解 ECC（Elliptic Curve Cryptography）中的离散对数问题，这在现代密码学中具有重要的实际意义。 欢迎来到《密码学核心算法实战》的 BSGS 算法二专题！这里没有纸上谈兵的理论空谈（真的不画大饼😉），只有一把把能直接撬动数据安全的精密齿轮⚙️。 ECC中的BSGS算法 🌟在 ECC 中，离散对数问题的形式是：给定一个椭圆曲线 $E$ 上的点 $P$ 和 $Q$，找到一个整数 $k$ 使得 $Q = kP$。这个问题被称为椭圆曲线离散对数问题（ECDLP），是 ECC 加密算法安全性的基础。而 BSGS 算法可以用来求解 ECDLP，从而在某些情况下破解 ECC 加密。 ECC中的BSGS算法的原理 😵既然有前一章的铺垫，那么原理就直接简单讲解了。 求解 $x$ 使得 $Q = xP$，我们可以将 $x$ 表示为 $x = ...
RSA加解密专题 - Coppersmith 相关攻击一
Coppersmith 攻击是一种针对 RSA 加密算法的攻击方法，主要用于在特定条件下恢复 RSA 私钥或解密 RSA 密文。该攻击方法由 Don Coppersmith 在 1996 年提出，利用了 RSA 加密算法中的数学结构和性质。 这里我们并不会深入到 Coppersmith 攻击的数学细节，但我们会介绍一些相关的攻击场景和原理，以帮助你理解 Coppersmith 攻击的基本思想和应用。 部分明文泄露攻击 😋单一变量的情况下，我们主要关注构建一个多项式方程，并使用 Coppersmith 方法来寻找小根。这种方法可以在某些特定条件下成功，例如当明文的某些部分已知或满足特定的数学关系时。 最简单的情况莫过于明文的某些部分已知，不管是哪一种泄露直接套用加密的方程就好： \begin{align*} (m_h + x)^e &\equiv c \pmod{n} \\ (m_h + x \ll m_l.\text{nbits}() + m_l)^e &\equiv c \pmod{n} \\ (x \ll m_l.\text{nbits}() + m_l)^e &\equi...
RSA加解密专题 - 公私钥格式相关攻击
pem 格式的文件通常用于数字证书认证机构(Certificate Authorities，CA)，其文件形式主要为 base64 编码的文件，头尾有类似于——-BEGIN PUBLIC KEY——-和——-END PUBLIC KEY——-的头尾标记 本文的目的就是如何从 .pem 格式的证书中，获取公钥、私钥信息。在 RSA 加密中，实际上公钥和私钥都是由一系列数字组成的，这些数字在.pem格式的证书中以特定的格式存储。通过解析这些数字，我们可以获取到公钥和私钥的相关信息，从而进行加密和解密操作。 PEM文件生成与使用 🥳在python中，可以通过 from Crypto.PublicKey import RSA 生成想要的公私钥文件。 生成公钥文件的代码如下： from Crypto.PublicKey import RSA from Crypto.Util.number import * p,q = getPrime(512),getPrime(512) n = p * q e = 0x10001 pub = RSA.construct((n,e)) with open...
密码学算法 - BSGS 算法一
当你在处理离散对数问题时，发现暴力破解的方法效率太低了😩，这时候 BSGS（Baby-Step Giant-Step）算法 就像一把神奇的钥匙🔑，能帮你快速找到离散对数的解。这个算法也别戏称为“北上广深”算法。🤐 欢迎来到《密码学核心算法实战》的 BSGS 专题！这里没有纸上谈兵的理论空谈（真的不画大饼😉），只有一把把能直接撬动数据安全的精密齿轮⚙️。 BSGS算法 🌟BSGS（Baby-Step Giant-Step）算法是一种用于求解离散对数问题的算法。给定质数 $p$，整数 $a$ 和 $b$，我们想要找到一个整数 $x$，使得 $a^x \equiv b \pmod{p}$（其中 $a$ 与 $p$ 互质）。 BSGS算法的原理 😵根据群中生成元的性质，我们可以知道元素 $a$ 的阶（即 $a$ 的幂等于 1 的最小正整数）是 $p-1$，然后产生一种循环的效果。因此，离散对数问题的解 $x$ 必须满足 $0 \leq x \leq p-1$。 我们考虑先求出一部分 $a$ 的幂次模 $p$ 意义下的值，将它们存起来，然后使得剩下没有求值的部分能够想个办法利用...
RSA加解密专题 - 私钥 d 相关攻击
在RSA加解密算法中，私钥是一个非常重要的参数，它与公钥指数和模数之间存在着密切的关系。如果私钥的选择不当，或者在某些特定情况下，攻击者可能会利用这些关系来破解RSA加密算法，从而获取到原始消息或者分解出模数。 本文将介绍一些与RSA私钥 $d$ 相关的攻击方法，包括常见的攻击手段如维纳攻击、$d_p$ 泄露攻击等。 $d_p$ 泄露攻击 😸在RSA算法中，私钥 $d$ 可以通过模数 $n$ 和公钥指数 $e$ 来计算得到。然而，如果攻击者能够获取到私钥的某些部分信息，例如 $d_p$（即 $d \mod (p-1)$），就可能会利用这些信息来破解RSA加密算法。 我们可以使用小费马定理：如果p是一个质数，整数a不是p的倍数，那么 $a^{p-1} \equiv 1 \mod p$ 根据 $d_p$ 的定义，我们有 $d \equiv d_p \mod (p-1)$，因此存在一个整数 $k$ 使得 $d = d_p + k(p-1)$。 带入RSA的加密解密公式，我们可以得到： a^{e×dp} \equiv a \cdot (a^{p-1})^k带入小费马定理得： a^{e×...
RSA加解密专题 - 公钥指数相关攻击
在实际应用中，攻击者可能会利用一些特定的攻击方法来破解RSA加密，尤其是当公钥指数选择不当时。 本文将介绍一些与 RSA 公钥指数相关的攻击方法，包括常见的攻击手段如小公钥攻击、共模攻击等。 共模攻击 😝对于同一个模数 $n$，用于加密同一个 $m$，但是用不同 $e$ 加密两次 \begin{align*} m^{e_1} \equiv c_1 \mod n \\ m^{e_2} \equiv c_2 \mod n \end{align*}使用裴蜀定理可以破解,构造 r e_1 + s e_2 = gcd(e_1,e_2)则由 c_{1}^r \cdot c_{2}^s \equiv m^{er_1 + se_2} \mod n从而绕过私钥d解密 共模攻击例题共模攻击例题下载 from Crypto.Util.number import * from secret import m n=22708078815885011462462049064339185898712439277226831073457888403129378547350292420267016551819...
RSA加解密专题 - 模数相关攻击
当你在 CTF 赛场遇到 RSA 题型时，模数相关的攻击手法⚔️往往是破解的关键。无论是共模攻击、模重复攻击，还是模数分解的相关漏洞，这些都是 RSA 加解密中常见且高频出现的题型。掌握这些攻击手法，不仅能让你在 CTF 赛场上如鱼得水，还能加深你对 RSA 加解密原理的理解。 暴力分解模数 🥳在 $N$ 的比特位数小于 512 的时候，可以采用大整数分解的策略获取 $p$ 和 $q$。一般来说，使用一些高效的分解工具（如 YAFU、msieve、CADO-NFS 等）可以在合理的时间内完成分解，获取 $p$ 和 $q$。 暴力分解模数例题暴力分解模数例题下载 from Crypto.Util.number import * from secret import M p = getPrime(56) q = getPrime(56) e = 65537 n = p * q long_M = long_to_bytes(M.encode()) C = pow(long_M, e, n) print(C) print(n) #n: 3211733906383171840011...
加解密模式分析 - ECC 加密算法
ECC（Elliptic Curve Cryptography）加密算法，作为非对称加密的现代方案之一，基于椭圆曲线上的离散对数问题的困难性，为数据加密和数字签名提供了高效且安全的解决方案。它在实际应用中被广泛采用，尤其是在资源受限的环境中，如移动设备和物联网设备。 在本章中，我们将深入分析 ECC 加密算法的核心原理和实现细节。我们将从 ECC 的数学基础开始，逐步揭示其加密和解密过程中的关键步骤。通过对 ECC 算法的详细解析，你将能够理解它是如何利用椭圆曲线上的离散对数问题的困难性来确保数据安全的。 ECC 加密数学原理 😇ECC 加密算法的安全性基于椭圆曲线上的离散对数问题的困难性。 椭圆曲线介绍首先，ECC 定义了一个椭圆曲线 $E_p$，通常采用 Weierstrass 形式的曲线，满足方程 $y^2 = x^3 + ax + b \mod p$，其中 $\Delta = -16(4a^3 + 27b^2) \neq 0$。 这个曲线的数学公式有点复杂，不过可以通过图像来理解。可以进入下面这个链接，改变参数来进行观察椭圆曲线的图像： 椭圆曲线图像 接下来我们介绍一下...
