``````title: "RSA 加密的基础"
subtitle: "「笔记」"
layout: post
author: "NagleZh"
lang: zh
tags:
- 笔记
``````

# GCD

GCD(A,B) A = qB + r

need proof: if A & B have same GCD, iff B & r have same GCD. so what we need proof is GCD(A, B) <=> GCD(B,r)

r = A - qB let’s say d|A , d|B A = dx, B = dy r = dx - q.dy = d(x-qy) => d|d(x-qy) so , if d|A & d|B , then d|r.

let’s say z|B & z|r A = qB + r B = zx , r = zy A = qzx + zy = z(qx + y) <=> z|z(ax + y)

# Congruences

definition:

``````a = b(mod n) if and only if:  n | (a-b)
``````

eg. 30 = 12 (mod 9)

1. `rem(30, 9) = 3 = rem(12, 9)`
2. `30 = 2*9 + 12`
3. `9 | ( 30 - 12 )`
4. `12(mod 9) = 3`

gcd(30, 12) = 212 + 6 gcd(12, 6) = 26

proof:

1. rem(a, b) = rem(b, n)

2.  what do we have? a = b(mod n) => n (a-b)
3. say a = x.n + r1 , b = y.n + r2

4.  n (x.n + r1 - y.n - r2)
5.  n n(x-y) +(r1-r2)
6. because r1 & r2 are reminders, so r1 - r2 < n

7. so, r1 == r2 is true.

Practice:

for now on, we have a problem need to be resolved: now , we know k, b. how to calculate a? a, k is a num between 0 - 26 rem(a.k, 26) a.k(mod 26) = r 26|(r - a.k) = 0

Application:

An application using a function to encrypt message. every single character is between a-z & A-Z, and it’s using methed like below:

take the index of single character A, and using a random num k(0< k <= 26)

rem((k * indexof(A)) ,26) = r

now , we do know what r , k is. how to decrypt the message?

encrypt function (presudo):

``````func encrypt(A string, k int) {
num := (indexof(A) - 65 * k) % 26 + 65
return char(num)
}
func decrypt(A string, k int) {
for (int i=0; i<=26; i++) {
num := ((indexof(A) - 65) - i * k) % 26
if (num == 0) {
return char(i + 65)
}
}
return "NULL"
}
``````