【密码学百科】数论进阶：二次剩余、椭圆曲线上的 Weil 配对
💡
原文中文，约23200字，阅读约需56分钟。
📝
内容提要
本文探讨了二次剩余理论与椭圆曲线上的配对映射在现代密码学中的重要性。二次剩余用于判断平方根的存在性和高效计算，而配对映射则支持身份加密和BLS签名等新型密码学构造。两者在椭圆曲线密码学中紧密结合，推动了密码学的发展。
🎯
关键要点
- 本文探讨了二次剩余理论与椭圆曲线上的配对映射在现代密码学中的重要性。
- 二次剩余用于判断平方根的存在性和高效计算，而配对映射则支持身份加密和BLS签名等新型密码学构造。
- 二次剩余理论提供了判断平方根存在性与高效计算平方根的工具。
- Weil配对是双线性映射的代表，开启了基于身份加密、BLS签名等密码学构造。
- Legendre符号用于刻画二次剩余性，具有完全积性。
- Euler判别法提供了计算Legendre符号的核心定理，极大提高了计算效率。
- Jacobi符号推广了Legendre符号的应用，适用于任意奇数模。
- 二次互反律是数论中的重要定理，描述了不同素数间的二次剩余关系。
- 二次剩余理论在密码学中有多方面应用，如Goldwasser-Micali加密方案和Blum-Blum-Shub伪随机数生成器。
- Tonelli-Shanks算法和Cipolla算法是计算模素数平方根的常用方法。
- 双线性映射是从两个群到第三个群的映射，具有双线性、非退化性和可计算性。
- Weil配对具有双线性、反对称和非退化等重要性质。
- Miller算法是计算Weil配对的核心算法，采用边计算边求值的策略。
- Tate配对和Ate配对是Weil配对的高效替代方案，具有更好的计算效率。
- 配对友好曲线是专门构造的椭圆曲线，适合用于配对密码学。
- 基于身份的加密和BLS签名是配对密码学的重要应用。
- MOV攻击利用配对将椭圆曲线上的离散对数问题归约为有限域上的离散对数问题。
- 安全参数选择需要综合考虑三个群的安全性，确保密码学构造的安全性。
❓
延伸问答
二次剩余理论在密码学中的应用有哪些？
二次剩余理论在密码学中应用于Goldwasser-Micali加密方案和Blum-Blum-Shub伪随机数生成器等。
Weil配对的主要性质是什么？
Weil配对具有双线性、反对称和非退化等重要性质。
如何计算模素数的平方根？
可以使用Tonelli-Shanks算法或Cipolla算法来计算模素数的平方根。
MOV攻击是如何利用配对的？
MOV攻击通过将椭圆曲线上的离散对数问题归约为有限域上的离散对数问题来利用配对。
双线性映射在密码学中的作用是什么？
双线性映射在密码学中用于实现基于身份的加密、BLS签名等新型密码学构造。
选择配对友好曲线时需要考虑哪些因素？
选择配对友好曲线时需考虑目标安全级别、嵌入度、曲线判别式及是否有成熟的实现等因素。
➡️
