密码学数学基础 - 群论基础

2026-02-19

密码学数学基础 - 前言

你有没有想过，当你在深夜网购🛒、和朋友发私密消息💬、或是登录银行账户🏦时，那些看似 “坚不可摧” 的安全屏障🔒，背后其实是一群数学精灵🧚在默默守护？✨ 欢迎来到《密码学数学基础》的奇妙世界！这里没有枯燥的公式堆砌（真的假的😋），只有一把把打开信息安全大门的钥匙🗝️。 在信息安全的宇宙🌌里，密码学就像是一位神秘的魔法师🧙，而数学则是它手中的魔法棒🪄。本系列文章将带你解锁密码学中最核心的数学知识，特别是数论和代数这两大 “护法”🛡️。从最基础的整除、同余，到高深莫测的群论、环论和域论，我们会一步步揭开这些数学工具的神秘面纱🎭。 别担心，我会用轻松有趣的方式（🤣👉🤡），让你发现这些看似高冷的数学概念，其实是设计和分析加密算法与协议的基石🧱。它们不仅是密码学的 “幕后英雄”🦸，还在编码理论、计算复杂性等领域大放异彩🌟。 想象一下：当你用 HTTPS 浏览网页时🌐，大素数的乘积正在帮你抵御窃听👂；当你用数字签名确认身份时✍️，椭圆曲线的点运算正在为你保驾护航🚢；当区块链上的交易被永久记录时⛓️，哈希函数的单向性正在守护数据的不可篡改性📜。这些听起...

2026-02-26

密码学算法 - Tonelli-Shanks 算法

当你在椭圆曲线上进行加密操作时📐，需要计算某个点的平方根，但又发现这个点在有限域中没有平方根时😱，别担心，这时候 Tonelli-Shanks 算法 就像一把灵巧的钥匙🔑，能帮你在无解的荒漠中精准定位那唯一的坐标点。 欢迎来到《密码学核心算法实战》的 Tonelli-Shanks 专题！这里没有纸上谈兵的理论空谈（真的不画大饼😉），只有一把把能直接撬动数据安全的精密齿轮⚙️。 Tonelli-Shanks算法 🌟Tonelli-Shanks 算法用于求解形如： x^2 \equiv a \pmod{p}的同余方程，其中 $ p $ 是奇素数，$ a $ 是模 $ p $ 下的平方数。 Tonelli-Shanks算法的操作 🙃输入：一个整数 $ a $ 和一个奇素数 $ p $，满足 $ a $ 是模 $ p $ 下的平方数。则 $ (\frac{a}{p}) = 1 $。输出：一个整数 $ x $，满足 $ x^2 \equiv a \pmod{p} $。 算法步骤： 将 $ p-1 $ 分解为 $ Q \cdot 2^s $，其中 $ Q $ 是奇数。（如果 ...

2026-03-14

密码学算法 - AMM 算法

当我们计算有限域下高次根式的求解时，AMM（Adleman-Manders-Miller）算法就派上了用场。AMM 算法是一种高效的算法，可以在多项式时间内求解有限域下的高次根式问题，这在密码学中有着重要的应用，比如在 RSA 加密算法中求解模 $n$ 下的 $e$ 次根式问题。 欢迎来到《密码学核心算法实战》的 AMM 算法专题！这里没有纸上谈兵的理论空谈（真的不画大饼😉），只有一把把能直接撬动数据安全的精密齿轮⚙️。 AMM 算法 🌟AMM 算法是密码学中专门用于在有限域 $\mathbb{F}_p$ 下求解高次根式的算法。给定一个质数 $p$，一个整数 $a$ 和一个正整数 $e$，我们想要找到一个整数 $x$，使得 $x^k \equiv a \mod p$。 要解之前，首先要先验满足条件： $a \equiv 0 \mod p$，此时 $x = 0$ 是一个解。 $a \not \equiv 0 \mod p$，要先验证解是否存在：a^{\frac{p-1}{\gcd(e, p-1)}} \equiv 1 \mod p AMM 算法的原理 😵首先设 $d = ...

2026-02-23

密码学数学基础 - 连分数

不知道大家前面的章节学习如何，相比以你的聪明才智，一定是轻松愉快的吧！😎 如果学废了，也别灰心，这一章的内容相对来说是独立的，跟前面章节的内容没有太大关系，所以如果你觉得前面章节的内容有点难以理解或者记忆，那么这一章你可以先跳过，等到后面章节需要用到的时候再回来学习这一章的内容也完全没有问题。😉 那么，这一章我们将介绍一个非常有用的工具，叫做连分数（Continued Fraction）。连分数在数论中有着广泛的应用，特别是在求解某些类型的方程和近似数值方面。我们将从连分数的定义开始，逐步深入到它的性质和应用，最后我们还会介绍一些与连分数相关的算法和技巧。🤗 连分数的定义和表示 🧐连分数是一种特殊的分数表示形式，它由一个整数部分和一个无限的分数部分组成。一个连分数可以表示为以下形式： a_0 + \frac{1}{a_1 + \frac{1}{a_2 + \frac{1}{a_3 + \cdots}}}其中 $a_0$ 是整数部分，$a_1, a_2, a_3, \ldots$ 是正整数，称为连分数的部分商。连分数可以用来表示实数，特别是无理数。对于一个实数 $x$，我们...

2026-03-02

密码学算法 - 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$ 意义下的值，将它们存起来，然后使得剩下没有求值的部分能够想个办法利用...

2026-02-28

密码学算法 - Miller-Rabin 素数检验

当你需要验证一个大数是否为素数时，Miller-Rabin 算法就像一位经验丰富的侦探🕵️‍♂️，能在短时间内给出一个可靠的答案，帮助你在数字的迷宫中找到真相。 欢迎来到《密码学核心算法实战》的 Miller-Rabin 素数检验算法专题！这里没有纸上谈兵的理论空谈（真的不画大饼😉），只有一把把能直接撬动数据安全的精密齿轮⚙️。 Miller-Rabin算法的原理 🌟Miller-Rabin算法基于两个数学定理： 费马小定理：如果 $p$ 是素数，且 $a$ 是一个整数，满足 $1 < a < p-1$，那么 $a^{p-1} \equiv 1 \mod p$。 二次剩余相关：如果 $p$ 是奇素数，方程 $x^2 \equiv 1 \mod p$，只有两个解 $x \equiv \pm 1 \mod p$。 首先，将待检验的奇数 $n$ 写成 $n-1 = 2^s \cdot d$ 的形式，其中 $d$ 是奇数。然后使用费马小定理： a^{n-1} \equiv a^{2^s \cdot d} \equiv (\ldots ((a^d)^2)^2 \ldo...