密码学前置内容 - Sage环境配置
在我们踏入密码学的神秘世界之前，首先要做好一个重要的准备工作：配置好我们的学习环境。就像一位冒险者需要一把锋利的剑和坚固的盾牌一样，我们也需要一个强大而灵活的工具来帮助我们理解和实践密码学中的各种算法和概念。而 SageMath 就是这样一个理想的工具，它不仅功能强大，还非常适合我们进行密码学相关的计算和实验。 SageMath 是一个开源的数学软件系统，集成了大量的数学库和工具，特别适合进行数论、代数、组合数学等领域的计算。对于我们学习密码学来说，SageMath 提供了丰富的函数和模块，可以帮助我们轻松地实现各种加密算法、数论函数、群论操作等。无论是计算大素数、求解同余方程，还是模拟加密协议，SageMath 都能为我们提供强大的支持。 如果只是简单安装使用 SageMath，那不用说了，直接上官网下载安装即可：SageMath官网 不过为了让大家能够更方便地使用 SageMath，我这里介绍一种在windows系统中VS Code使用 SageMath 的方法，这样我们就可以在一个熟悉的环境中进行密码学的学习和实践了。 下载VS Code和配置python环境 🥰这里有大...
密码学数学基础 - 连分数
不知道大家前面的章节学习如何，相比以你的聪明才智，一定是轻松愉快的吧！😎 如果学废了，也别灰心，这一章的内容相对来说是独立的，跟前面章节的内容没有太大关系，所以如果你觉得前面章节的内容有点难以理解或者记忆，那么这一章你可以先跳过，等到后面章节需要用到的时候再回来学习这一章的内容也完全没有问题。😉 那么，这一章我们将介绍一个非常有用的工具，叫做连分数（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$，我们...
密码学数学基础 - 扩展二次剩余
前一章中，我们主要聚焦于单一素数模数下的二次剩余问题，这为我们理解二次剩余奠定了坚实的基础。然而，在实际应用中，我们经常会遇到更复杂的情况，比如模数是合数或者有多个素因数的情况。在本章中，我们将扩展我们的视野，探讨这些更一般的二次剩余问题。 这章比较难，跟进我的步伐，Go~~~🚀 扩展模数与雅可比符号 😵💫当模数为 $p^k$，其中 $p$ 是奇素数，$k \geq 1$ 时，我们可以通过扩展勒让德符号来判断一个数是否是模 $p^k$ 的二次剩余。对于一个整数 $a$ 和一个奇素数 $p$，我们定义： \left( \frac{a}{p^k} \right) = \left( \frac{a}{p} \right)^{k}其中 $\left( \frac{a}{p} \right)$ 是勒让德符号。 雅可比符号可以看作是勒让德符号的推广。对于一个整数 $a$ 和一个正整数 $n = p_1^{k_1} p_2^{k_2} \cdots p_m^{k_m}$，雅可比符号定义如下： \left( \frac{a}{n} \right) = \prod_{i=1}^{m} \l...
密码学数学基础 - 二次剩余
在前两章中，我们已经掌握了整数关系和同余关系的基本概念，这些工具为我们理解数字之间的关系奠定了基础。而在本章中，我们将进入一个更深层次的领域：二次剩余。 本章存在大量定理和证明，虽然有些定理的证明可能比较复杂，但我们会尽量用通俗易懂的语言来解释这些概念。😎 剩余类与欧拉函数 🧐剩余类是指在模运算下具有相同余数的整数集合，我们用$Z_n$表示这个集合。对于一个模数 $n$，剩余类可以表示为 ${[0], [1], [2], \ldots, [n-1]}$，每个整数都属于其中一个剩余类。定义$Z^*_n = {a \in Z_n | \gcd(a,n) = 1}$，即在模 $n$ 下与 $n$ 互质的剩余类集合。 欧拉函数 $\phi(n)$ 是指在模 $n$ 下与 $n$ 互质的整数的数量，即$Z^*_n$的元素个数。对于一个正整数 $n$，如果 $n$ 的质因数分解为 $n = p_1^{k_1} p_2^{k_2} \cdots p_m^{k_m} = n_1 n_2 \cdots n_m$，其中 $p_i$ 是 $n$ 的不同质因数，$k_i$ 是对应的正整数（实际上这里...
密码学数学基础 - 同余关系与模运算
在上一章中，我们探讨了整数关系的基本概念，这些工具为我们理解数字之间的关系奠定了基础。而在本章中，我们将进入一个更深层次的领域：同余关系与模运算。这些概念不仅是数论中的重要内容，也是密码学中不可或缺的工具。 同余关系和模运算为我们提供了一种新的视角来看待整数之间的关系。它们让我们能够在一个有限的范围内进行计算，这对于设计和分析加密算法来说至关重要。无论是经典的凯撒密码，还是现代的 RSA 加密算法，同余关系和模运算都在其中扮演着重要的角色。 这个章节初步认识模这个重要概念，一定要跟上哦~~~🚀 模运算与同余关系 🥰模运算是一种数学运算，它将一个数除以另一个数，并返回余数。我们用符号 $mod$ 来表示模运算。设$a=bq+r$，其中 $r$ 是余数，那么我们说 $a \equiv r \mod b$。例如，$7 \mod 3$ 的结果是 $1$，因为 $7$ 除以 $3$ 的商是 $2$，余数是 $1$。 可以看出，模和整除是密切相关的。模运算可以看作是整除的一种扩展，它不仅告诉我们一个数是否能被另一个数整除，还告诉我们在不能整除的情况下，余数是什么。因此，模运算将整数映射到...
密码学数学基础 - 整数关系
在我们踏上密码学数学基础的冒险之旅后，第一站就是整数关系的世界。这个领域虽然看似简单，但却是构建整个密码学大厦的基石。无论是最基本的整除关系，还是更复杂的同余关系，它们都在为我们揭示数字之间的神秘联系。 本章将带你深入了解整数关系的核心概念，包括整除、素数、最大公约数和最小公倍数等。我们将通过生动的例子和直观的解释，帮助你掌握这些基本工具，为后续的密码学学习打下坚实的基础。 别看我说的很高大上，放轻松，这一章真的非常简单口牙。😁 整除关系与素数 😋在整数的世界里，整除关系是最基本的关系之一。我们说一个整数 $ a $ 整除另一个整数 $ b $，记作 $ a \mid b $，如果存在一个整数 $ k $ 使得 $ b = ak $。换句话说，$ b $ 可以被 $ a $ 整除，没有余数。例如，$ 3 \mid 12 $ 因为 $ 12 = 3 \times 4 $，但 $ 5 \nmid 12 $ 因为 $ 12 $ 不能被 $ 5 $ 整除。 素数是大于 1 的整数，除了 1 和它本身之外没有其他正整数因数。素数在密码学中扮演着重要的角色，因为许多加密算法都依赖于大素数...
密码学数学基础 - 前言
你有没有想过，当你在深夜网购🛒、和朋友发私密消息💬、或是登录银行账户🏦时，那些看似 “坚不可摧” 的安全屏障🔒，背后其实是一群数学精灵🧚在默默守护？✨ 欢迎来到《密码学数学基础》的奇妙世界！这里没有枯燥的公式堆砌（真的假的😋），只有一把把打开信息安全大门的钥匙🗝️。 在信息安全的宇宙🌌里，密码学就像是一位神秘的魔法师🧙，而数学则是它手中的魔法棒🪄。本系列文章将带你解锁密码学中最核心的数学知识，特别是数论和代数这两大 “护法”🛡️。从最基础的整除、同余，到高深莫测的群论、环论和域论，我们会一步步揭开这些数学工具的神秘面纱🎭。 别担心，我会用轻松有趣的方式（🤣👉🤡），让你发现这些看似高冷的数学概念，其实是设计和分析加密算法与协议的基石🧱。它们不仅是密码学的 “幕后英雄”🦸，还在编码理论、计算复杂性等领域大放异彩🌟。 想象一下：当你用 HTTPS 浏览网页时🌐，大素数的乘积正在帮你抵御窃听👂；当你用数字签名确认身份时✍️，椭圆曲线的点运算正在为你保驾护航🚢；当区块链上的交易被永久记录时⛓️，哈希函数的单向性正在守护数据的不可篡改性📜。这些听起...
