My note when previewing Copying the Textbook of abstract algebra.

Chapter 7: Introduction to Cryptography

  • Plaintext (明文)
  • Ciphertext (密文)
  • Cryptosystem or Cipher (密码)
  • Encryption and Decryption (加密&解密)
  • Key (密钥)

Private Key Cryptography

  • Private Key Cryptography (单钥/私钥加密)

    The same key is used for both encrypting and decrypting messages

  • Monoalphabetic Cryptosystems (单字母密码系统/移位码)

    A character in the enciphered message represents exactly one character in the original message.

  • Simple Shift Code (简单移位码)

    $$f(p)=p+b\textrm{ mod } 26$$

  • Affine Cryptosystem (仿射密码系统)

    $\textrm{gcd}(a,26)=1$:
    $$f(p) = ap+b\textrm{ mod } 26$$

  • Polyalphabetic Cryptosystem (多字母密码系统)

    A ciphertext letter could represent more than one plaintext letter
    $\mathrm{A}\in\mathrm{M}_{2\times 2}$:
    $$f(\vec{p})=\mathrm{A}\vec{p}+\vec{b}$$

Public Key Cryptography

The RSA Cryptosystem

  • RSA Cryptosystem

    1. Find BIG primes $p$ and $q$
    2. $n=pq$ and $m=(p-1)(q-1)=\phi(n)$
    3. $\textrm{gcd}(E,m)=1$ for randomly selected $E$
    4. Find $D$ using Euclidean Algorithm that $DE\equiv 1(\textrm{mod }m)$
    5. $n$ and $E$ are public

  • RSA Encryption & Decryption

    1. Message is encoded and splitted into $x<n$
    2. Encrypted message is $y=x^E$
    3. Decrypted message is $x=y^D\textrm{ mod }n$

Message Verification

  • How it work
    1. Alice: $(n,E,D)$
    2. Bob: $(n’,E’,D’)$
    3. $x’=x^{D’}\textrm{ mod }n’$
      • A message that anyone can decrypt by encrypting it with $E’$
      • Can only be generated by Bob
    4. $y’=x’^{E}\textrm{ mod }n$
      • A message only Alice can decrypt
      • The message to be sent to Alice
      • Alice can read it with Bob’s Public key, and be sure of that it is sent by Bob