加密学之贰 - Group & Number Theory

COMP3357 digest 的 P2 部分,主要介绍群论 (group theory),数论 (number theory) 的相关知识以及它们在加密学中的应用。

该部分的内容主要是为了 P3 部分做铺垫:P3 中的困难问题 (hard problems) 与单向函数 (one-way function) 的构建与这一节里提到的数论/群论知识存在紧密的联系。

同样,与 CnBlogs 中的笔记不同,这里不会详细的记载每个相关的知识点;只会尝试简略地总结一些能让未来的自己也会感到有趣,巧妙的内容 (Eureka!)。


  This article is a self-administered course note.

  It will NOT cover any exam or assignment related content.


Multiplicative Inverse

Definition. If for a given integer b, there exists an integer c such that bc=1modN, we say that b is invertible modulo N, and call c a multiplicative inverse of b modulo N.

The multiplicative inverse is NOT unique. For an invertible b, if c is an inverse of b, every x congruent with c modulo N is also an inverse of b. (xcmodN). We use b1 to denote the inverse of b that b1{1,2,...N1}.

Theorem. Let b,N be integers, with b1, and N>1. Then b is invertible modulo N if and only if b is relatively prime to N. Note that integers b,N are relatively prime (or coprime) means gcd(b,N)=1.

Therefore, for a prime p, every b{1,2,...p1} is invertible modulo p.

The above theorem could be proved by applying Bezout's identity: it states that for every positive integer a,b, there exists a pair of integers X,Y that Xa+Yb=gcd(a,b).


Eureka moment!

逆元这个概念算是老熟人了;它将模意义下的除法转化为乘法

求逆元的常见方法:扩展欧几里得算法,欧拉定理,费马小定理。这些方法在接下来都会进行介绍。


Euler's Totient Function

Definition. Euler's Totient Function φ(N) is defined as the number of positive integers N that are relatively prime to N, where 1 is counted as being relatively prime to all integers.

The general case of Euler's Totient is φ(n)=nΠp|n(11p)=n(11p1)(11p2)...(11pr). This is essentially the Inclusion-Exclusion principle.

Code Implementation: Linear Sieve

To calculate a specific totient of n, we could design a trivial O(nlogn) algorithm based on the above formula. However, there exists a sieve algorithm that could calculate totients of number 1 to n in linear time O(n). Below is the code in C++:

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
// the Euler sieve
// bool array: is_prime, int array: prime, phi

void sieve() {
for (int i = 1; i < N; ++i) is_prime[i] = 1;
cnt = 0;
is_prime[1] = 0;
phi[1] = 1;
for (int i = 2; i <= N; ++i) {
if (is_prime[i]) {
prime[++cnt] = i;
phi[i] = i - 1; // for a prime p, phi[p] = p - 1
}
for (int j = 1; j <= cnt && i * prime[j] <= N; ++j) {
is_prime[i * prime[j]] = 0;
if (i % prime[j])
phi[i * prime[j]] = phi[i] * phi[prime[j]];
else {
phi[i * prime[j]] = phi[i] * prime[j];
break;
}
}
}
}

Reference & Explanation: (OI Wiki) Linear Sieve for Euler's totient function

Euler's Theorem

Theorem. Let n be a positive integer, and let a be an integer that is relatively prime to n. Then aφ(n)1(modn), where φ(n) is Euler's totient function of n.

Since gcd(a,n)=1, a is invertible modulo n. According to Euler's Theorem, aφ(n)1(modn). Therefore a×aφ(n)11(modn). aφ(n)1 is a multiplicative inverse of a modulo n.

An informal proof. (need the knowledge of Zn, multiplicative group of integers modulo n).

For aZn, {r1,r2,...rφ(n)}=(Z/n)={ar1,ar2,...arφ(n)}.

Therefore r1r2...rφ(n)(ar1)(ar2)...(arφ(n)), which reduces to 1aφ(n). This cancellation is allowed since all ri have multiplicative inverses modulo n.

Reference & Explanation: (Brilliant Math Wiki) Proof of Euler's Theorem


Eureka moment!

欧拉函数也接触了很长一段时间了,刻在 DNA 里的 φ1=Id

这里主要想讲下关于欧拉函数的一般公式:φ(n)=nΠp|n(11p)。本质上这是一个容斥原理的应用。

举个例子就容易理解了:假设 n 只有两个质因子 p1,p2,那么展开上式可得 φ(n)=nnp1np2+np1p2. 用自然语言描述,即在 1n 中与 n 互质的数的个数为 n 减去是 p1 倍数的数的个数,再减去是 p2 倍数的数的个数。此时,是 p1p2 倍数的数将会被重复减去两次;根据容斥原理,我们将多减的个数重新加回来,因此最后再加上是 p1p2 倍数的数的个数。

关于欧拉函数线性筛算法的设计也十分巧妙,它是建立在质数线性筛的基础上的。具体可见 OI Wiki 中的相关解释,讲的很清楚。


Extended Euclidean Algorithm (eGCD)

Euclidean Algorithm (辗转相除法) is one of the oldest and most widely known algorithms. It is a O(logn) method of computing the greatest common divisor (GCD) of two integers a,b.

According to Bezout's Identity, there exists integers X and Y that Xa+Yb=gcd(a,b) given a,b. The extended Euclidean algorithm is the method of computing such X and Y.

Assuming two adjacent levels in the GCD recursive process:

current X current Y current a current b
unknown X unknown Y a b
known X known Y b a%b

(1)Xa+Yb=Xb+Y(a%b)Xa+Yb=Xb+Y(aabb)Xa+Yb=Ya+(XYab)b

Therefore X=Y,Y=XYab.

Code Implementation

1
2
3
4
5
6
7
8
9
10
int exgcd(int a, int b, int& x, int& y) {
if (b == 0) {
x = 1, y = 0;
return a;
}
int gcd = exgcd(b, a % b, x, y);
int _x = x;
x = y, y = _x - y * a / b; // from the above equities
return gcd;
}

Using eGCD to get Inverse

Given b,N, if gcd(b,N)=1, b is invertible modulo N. We could apply eGCD algorithm to find multiplicative inverse of b modulo N.

Run the above function exgcd(b,N,x,y), we could obtain x and y that xb+yN=gcd(b,N)=1. Therefore xb1(modN). x is a multiplicative inverse of b modulo N.


Eureka moment!

不得不感叹聪明的人与时代无关。这一这么古老的算法也花了我一段时间去弄懂。

无论是 GCD 还是 exGCD,其核心在于欧几里得公式 gcd(a,b)=gcd(b,a%b). exGCD 只是在这一基础上结合了裴蜀定理递推计算对应的 xy

这里提供一个非正式的证明:首先是一个基本事实:对于互质的 k1,k2k1%k2,k2 也一定互质。这一为了方便用群论的知识做个解释:gcd(k1,k2)=1, 所以 k1(Z/k2)。自然 k1%k2(Z/k2),所以 gcd(k1%k2,k2)=1

那么对于任意正整数 a,b,设 d=gcd(a,b),则有 a=k1d,b=k2d,且 gcd(k1,k2)=1. 那么 a%b=aabb=ak1k2b=k1dk1k2k2d=(k1%k2)d。根据上面的事实,我们有 gcd(k2,k1%k2)=1,所以 gcd(b,a%b)=dgcd(k2,k1%k2)=d


Chinese Remainder Theorem (CRT)

今有物不知其数,三三数之剩二,五五数之剩三,七七数之剩二,问物几何? —— 孙子算经

The Chinese remainder theorem (CRT) is a theorem which gives a unique solution to a simultaneous linear congruences with coprime moduli. In its basic form, the CRT will determine a number p that, when divided by some given divisors, leaves given remainders.

If m1,...,mk are pairwise coprime, i.e., gcd(mi,mj)=1 for ij, then the following system (2){ xa1(modm1) xa2(modm2) ..., xak(modmk) has exactly one solution in the sense of module M=Πi=1kmi for any a1,a2,...,akZ.

We define Mi=M/mi and tiMi1(modmi), then the solution to this congruences is xi=1kaiMiti(modM). Note that x is unique modulo M.

The proof of correctness and uniqueness of CRT: My CnBlogs or OI Wiki-CRT

Code Implementation

1
2
3
4
5
6
7
8
9
10
11
long long CRT(int k, long long* a, long long* m) {
long long M = 1, ans = 0;
for (int i = 1; i <= k; ++i)
M = M * m[i];
for (int i = 1; i <= k; ++i) {
long long Mi = M / m[i], ti, _;
exgcd(Mi, m[i], ti, _); // get inverse: ti * Mi mod m[i] = 1
ans = (ans + a[i] * Mi % M * ti % M) % M;
}
return (ans % M + M) % M;
}


Eureka moment!

数论的定理多如牛毛,在众多熟悉或不熟悉的外国名字中看到一个「中国」剩余定理还是非常之亲切的。

CRT 提供了互质模数的线性同余方程组的解。在密码学中 CRT 经常被运用于简化模意义下求幂的运算。具体来说,对于合数模数 Mgcd(M,a)1 的情况,可以应用 CRT 简化 aemodM 的计算。此外,CRT 还能用于加速 RSA 的解密过程 (RSA decryption)(3)m=cdmodN{mcdmodpmcdmodq{m(cmodp)dmod(p1)modpm(cmodq)dmod(q1)modq Bob (Receiver) 是知道 N 的两个 factor pq 的,因此其先将朴素的解密过程转化为这一线性同余方程组,并应用 CRT 得到方程的解,也即消息 m。这一解密方式比直接计算 cdmodN 快了 4左右。

P.S. RSA 问题是一个著名的困难问题 (hard problems),我将会在 P3 中进行介绍。


Quadratic Residue

If there is an integer 0<x<p such that x2a(modp). We call a a quadratic residue modulo p. Otherwise (such x doesn't exist), we call a a quadratic nonresidue modulo p.

Note that pa to exclude the trivial cases x=0.

The quadratic residue problem requires us to solve the congrence x2a(modp). Essentially it is to find the square root of a in the sense of modulo p. Usually, the moduli p is an odd prime.

Legendre Symbol

The legendre symbol is a number theoretic function (ap) which is defined to be equal to ±1 depending on whether a is a quadratic residue modulo p. (4)(ap)=(a|p)={ 0, if  p|a 1, if a is a quadratic residue modulo p1, if a is a quadratic nonresidue modulo p

### Euler's Criterion

For an odd prime p and pa, the Legendre symbol (ap)a(p1)/2(modp).

For an odd prime p and pa, according to Euler's critetion, we could determine whether a is a quadratic residue modulo p by checking whether a(p1)/2modp equals to 1 or not.

See the prove here.


Eureka moment!

虽然在本课程中关于二次剩余问题的内容只是浅尝辄止,但我觉得还是非常有必要将其单独拿出来进行介绍,因为这个问题的研究在数论上占有举足轻重的地位。

二次剩余问题本质上是模意义下的开根问题,实际上是 RSA 问题的铺垫:RSA 问题本质上是模意义下的开 e 次根问题。因此,当 e=2 时,RSA 问题与二次剩余问题等价。


Group Theory: Introduction

Group theory is the study of groups. Groups are sets equipped with an operation that satisfies certain basic properties. They are closure, identity, inverse, and associativity.

Set G and a binary operation defined on G that:

  • Closure: For all g1,g2G, it holds that g1g2G
  • Identity: There exists an identity element eG s.t. eg=g=ge for all gG
  • Inverse: For every element gG there exists an inverse element hG s.t. gh=e=hg
  • Associativity: For all g1,g2,g3G, g1(g2g3)=(g1g2)g3

Order of a finite group G, denoted |G|, is the number of elements in G.

If group G is an Abelian group, it will satisfiy the additionally commutativity: For all g1,g2G, g1g2=g2g1.

Subgroups

Definition. If G is a group, a set HG is a subgroup of G if H itself forms a group under the same operation. H is a strict subgroup of G if HG.

Note that every group G always has the trivial subgroups G and {e}.

Modulo Multiplication Group

A modulo multiplication group (Z/n) is a finite group of residue classes prime to n under multiplication mod n. (Z/n) is Abelian of group order φ(n), where φ(n) is the totient function.

The multiplicative group of integers modulo n, (Z/n), is very worth researching.

(Z/n):= invertible elements in {1,2,...n1} := {b{1,...,n1}|gcd(b,n)=1}.

Therefore |(Z/n)|=φ(n). If n is prime (which is usually denoted p), |(Z/p)|=p1.

(Z/n) is also denoted Zn.


Eureka moment!

群论虽然是第一次接触学习,但它的定义与相关的一些定理意外的容易理解 (遵循直觉)。 可能是由于 "群" 这一概念在日常生活中已经渗透得很深,以致于抽象成为数学模型后也有较强的既视感。

这里想要重点提一下整数模 n 乘法群 (Z/n),这是一个很重要的群。对于它的研究起源于对模 n 剩余类 (residue classes) 的研究。我们知道,对于模 n 剩余类 {0,1,2,...,n1},若群运算 (group operation) 是加法 +,剩余类能够很自然的形成一个群 (Z/n)+。然而,若我们将群运算设为乘法 ×,剩余类并不能形成一个群。这是因为群性质要求每个群元素都具有逆元 (inverse);而在模 n 剩余类中,只有与 n 互质的群元素才有逆元。因此,我们将与 n 不互质的元素剔除,剩下的就是整数模 n 乘法群 (Z/n) 了。


Fermat's Little Theorem

Theorem. Let G be a finite group of order m=|G|. Then for any gG, it holds that gm=1.

Proof. G={g1,g2,...,gm}, gG. gigj for all i,j, therefore ggiggj for all i,j. With the closure property of the group G, {gg1,gg2,...ggm} is a permutation of {g1,g2,...,gm}. Then we have (gg1)(gg2)...(ggm)=g1g2...gm, which could be reduced to gm=1.

We could see the similarity between the proof of Fermat's little theorem and Euler's theorem. In fact, Fermat's little theorem is the general form of Euler's theorem. Let G be the modulo multiplication group (Z/n), one could derive the Euler's theorem.

Corollary 1

Corollary (Fermat's Little Theorem). Let G be a finite group of order m. Then for any gG, and any integer x, we have gx=g[xmodm].

Many exponents calculation could be simplified using this corollary.

For example, if computing 51000mod11, we could see 5(Z/11) since gcd(5,11)=1. Therefore 51000mod11=5[1000modφ(11)]mod11=5[1000mod10]mod11=1.

Corollary 2

Corollary (Fermat's Little Theorem). Let G be a finite group of order m. Let e>0 be an integer, and define the function, fe:GG by fe(g)=ge.

  • If gcd(e,m)=1, then fe is a permutation, i.e., a bijection.
  • Moreover, if d=e1modm, then fd is the inverse of fe.


Eureka moment!

注意,我们这里介绍的是费马小定理的群论表述;事实上,其拥有一个更为广为人知的数学表述。对于任意整数 a, 质数 p,有 apa(modp)

gcd(a,p)=1 时,我们能够由此推导出欧拉定理。

gcd(a,p)1 时,由于 p 是质数,a 一定是 p 的倍数 p|a. 那么显然此时 apa0(modp).


Cyclic Groups and Generators

Before stepping into the definition of cyclic groups, we introduce the definition of order of a group element.

Definition. The order of a group element gG is the smallest positive integer r such that gr=1, and is denoted by ord(g).

Note the distinction between the two concepts the order of a group and the order of a group element.

Definition. If an element gG has order |G|, then G is a cyclic group and can be denoted by G=g. We call g the generator of G.

Therefore, if G is a cyclic group and |G|=m, there must exists a generator gG that could generate the whole group by constantly multiplying itself, i.e., {g,g2,...,gm}=G.


Eureka moment!

之前搞 OI 的时候在数论里学习到了原根 (primitive root) 的概念,然而并不是很明白。到大学学到生成元 (generator) 的概念突然有了醍醐灌顶之感。实际上,原根和生成元的概念是一体两面。

若一个正整数 m 有原根 g,那么就意味着群 (Z/m) 是一个循环群,且它的生成元为 g

正整数 m 有原根 (群 (Z/m) 为循环群) 的充要条件为:它能表达为下列形式之一 2,4,pn,2pn,其中 p 为奇素数。且若 m 有原根,其原根的个数为 φ(φ(m))。部分证明 (m 为质数) 见我的 CnBlogs: 循环群;这里还提到,任意质数阶群 (group of prime order) 一定是循环群


Reference

  This article is a self-administered course note.

  References in the article are from corresponding course materials if not specified.

Course info:

Code: COMP3357, Lecturer: Dr. Ravi. Ramanathan, TA: Zhang Chengru

Course textbook:

Introduction to Modern Cryptography (2nd edition), Katz, J. & Lindell, Y., (2015), CRC Press, view

Math content:

OI Wiki, Brilliant Math Wiki, Wolframe MathWorld.

-----------------------------------そして、次の曲が始まるのです。-----------------------------------