基于模二次剩余的对称与非对称加密算法

首先介绍有关模二次剩余的相关数论基础。然后介绍了BBS伪随机数发生器的构造以及使用BBS PRNG的对称机密系统。此外介绍因数分解假设以外的另一种假设——二次剩余假设在公钥密码系统的应用,即Rabin算法。

二次剩余的数论基础

二次剩余的定义

QR_n \coloneqq {x \in Z_n^* \ | \ \exists y \in Z_n^*: y^2 \equiv x \ \ mod \ n}

给定模n乘法群,如果对于x \in Z_n^*,存在群元素y满足y^2 = x,则x是一个二次剩余,此时y是x的一个根。QR_n是模n二次剩余的集合。

一个元素不是二次剩余就是二次非剩余,集合记作QNR_n

QR_n乘法群

对于QR_n的元素x_1x_2有以下性质:

  • x_1 \cdot x_2 \in QR_n

    两个群元相乘结果仍在群中

  • x_1^{-1} \in QR_n

    存在逆元

素数模二次剩余Z_p^*

当p>2且为素数时,Z_p^*中每个二次剩余都有两个平方根。因此平方取模的函数具有“二对一”的映射关系,这意味着Z_p*中恰好有一半的元素为二次剩余,也即|QR_p| = \frac{p-1}{2}

讲义上给出的是Z_p域,有小于等于2个根。

x \not\equiv 0, p \ne 2时,有0或2个根。

Jacobi符号

设p>2且为素数,x \in Z_p^*,Jacobi符号定义为:

\Bigl(\frac{x}{p}\Bigr) \coloneqq \begin{cases}
    1 &\text{if } x \in QR_p\\
    -1 &\text{else}
\end{cases}

实际上还有一个符号称为Legendre符号,要求模数必须为奇素数。而Jacobi符号的模数可以是任何正整数。所以Jacobi符号是Legendre符号的推广,当模数为奇素数时,Jacobi符号等于Legendre符号。

欧拉准则 Euler Criterion(模p二次剩余的判断)

\Bigl(\frac{x}{p}\Bigr) \equiv x^{\frac{p-1}{2}} mod p

欧拉准则用于判断x是否是素数p的二次剩余

继续阅读“基于模二次剩余的对称与非对称加密算法”

分组密码工作模式

根据每次加密的单位数据长度可以将对称加密算法分为流密码(Stream Cipher)和分组密码(Block Cipher)。本文讨论分组密码中算法对数据分组加解密的几种不同处理方式,称为分组密码的工作模式。

分组密码与流密码

分组密码

分组密码中,明文被分成长度相等的分组,若末尾不够组成一个分组则使用预设的内容进行填充,然后用相同的算法进行加密并组合形成密文。

分组密码包含以下几种常见的工作模式:

  • ECB(Electronic Codebook,电子密码本)
  • CBC(Cipher Block Chaining,密码分组链接)
  • CFB(Cipher Feedback,密码反馈)
  • OFB(Output FeedBack,输出反馈)
  • CTR(Counter,整数计数)
  • PCBC(Plain/Propagating Cipher Block Chaining,明文密码分组链接)
  • OCFB(Output Cipher FeedBack,输出密码反馈)

流密码

因为会介绍到具有流密码相似性质的CBC、CFB和OFB,所以顺便介绍一下流密码的分类。

流密码总体分为两类:同步流密码和自同步流密码(也即异步流密码)。

同步流密码
同步流密码指在该密码系统中,密钥流的生成独立明文消息和密文。同步要求严格,需要无错误传播,单个字符的错误不影响其他位。

自同步(self synchronization)流密码或异步流密码
其特点是具有记忆元件,密钥流由密钥和固定数量的之前的密文字符生成。自同步流密码在由于插入、删除或替换导致失去同步后,接受端接收到一定数量的正确密文后可以自动恢复同步,同步后的密文可以正常被解密。

继续阅读“分组密码工作模式”

密码学健壮的系统与RSA

Cryptographically Strong Systems

密码学健壮的系统:
使用复杂的数学问题设计密码系统,使破解密码系统的难度和求解此类数学问题的难度一样大。

数学秘密:用于解密、签名等等
素数在许多密码系统(尤其是非对称密码系统)中发挥重要作用

假设

因数分解假设(Factorization)
n = p \cdot q
已知n,难以找到p和q两个素数(当p、q足够大时难以暴力破解)
n是密钥对的公开部分。

此外还应该有一些特殊的属性:
例如模m同余:
a \equiv b \mod m

RSA算法中计算模反元素即找到与e同余的一个数

继续阅读“密码学健壮的系统与RSA”

Authentication 身份认证:Admission and Access Control

认证:准入与访问控制

Admission Control 准入控制:只与授权的对象通信

Access Control 访问控制:只能在授权的对象上执行操作

密码散列函数(Cryptographic Hash Function/哈希函数)

单向函数

对于单向函数f:

  • 计算f(x) = y很容易
  • 而计算f^{-1}(y) = x很难

密码散列函数是单向函数。

密码散列函数的属性

碰撞抗性 Collision resistance

很难找到一对x和y,使得h(y) = h(x)y \not = x

即无法从计算角度找到任何两个哈希值都相同的独特输入。

原像抗性 Preimage resistance

在集合论中,给定一个从集合X到集合Y的映射,x属于定义域X,y属于值域Y:

  • x在该映射下有f(x)=y,则y称为x在该映射下的像
  • x称为y的原像

此处原像指散列函数的输入。

因此原像抗性指:给定散列函数的输出y,从计算角度无法找到符合该输出的输入值x,即无法计算f^{-1}(y) = x

第二原像抗性/弱碰撞抗性 Second-preimage resistance/Weak collision resistance

第二原像指另一个输入x’,使h(x') = h(x),且x' \not = x

因此第二原像抗性(或称之为弱碰撞抗性)指:给定x和散列函数h,从计算角度无法找到任何与x有着相同输出的二次输入值x’。

继续阅读“Authentication 身份认证:Admission and Access Control”

信息安全基础

本文介绍了保护目标、攻击者模型以及保护方法中非密码学部分的基础知识。

学习目标

  • 诚实以及现实的自我评估

  • 对其他人、公司、组织等的评估

  • 收集信息安全和数据保护需求的能力

    • 保护目标
    • 攻击者模型与信任模型
  • Validation & Verification,及实际和理论限制

    Validation指是否满足需求,Verification指是否符合规范

    "Validation. The assurance that a product, service, or system meets the needs of the customer and other identified stakeholders. It often involves acceptance and suitability with external customers. Contrast with verification."
    "Verification. The evaluation of whether or not a product, service, or system complies with a regulation, requirement, specification, or imposed condition. It is often an internal process. Contrast with validation."

  • 信息安全和数据保护机制(理解并开发)

继续阅读“信息安全基础”