[GEMATMW] Module 4: Mathematics in Digital Communications

Cryptosystem

relay an information from one place to another without anyone else being able to know it

Encryption

process of using an algorithm to transform information into a format that cannot be read

Decryption

process of using another algorithm to transform encrypted information back into a readable format

plain text

original information

cipher text

encrypted version

Confidentiality
Integrity
Authenticity
Non-repudiation

4 Objectives of Encryption

Confidentiality

sender and receiver can be assured that no third party can read the message

Integrity

sender and receiver can be sure that no third party can make changes in the message

Authenticity

receiver can be sure that it is the sender who sent the message

Non-repudiation

receiver can prove to any third party that the sender sent the message

Caesar’s Cipher

cipher that shifts letters to 3 (A → D)

Vigenère Cipher

substitution cipher where a different alphabet was used for the next letter of the message, with the alphabets repeating periodically according to some key

Mono-Alphabetic Cipher System

cipher system that shifts all letters n times

Poly-Alphabetic Cipher System

shifting of letters are not defined

Symmetric encryption

secret key encryption; uses one key for encryption and decryption

Asymmetric encryption

public key cryptosystem; uses a public key for encryption and a separate private key for decryption

Public Key Cryptosystem

(1976) W. Diffie and M. Hellman

Public Key Cryptosystem

each individual is assigned public and private keys to encrypt and decrypt information; a message encrypted by the public key can only be decrypted by the private key

Public key

available for others to use when encrypting information; people can use that individual's key to decrypt information

Private key

accessible only to the individual; the individual can use this key to decrypt any message encrypted with the other key

Modular arithmetic

a ≡ b (mod n); a is congruent to b modulo n

RSA Cryptosystem

Rivest, Shamir, Adleman

RSA Cryptosystem

based on the assumption that factoring large integers is computationally hard

Trap door function

one-way function; a function that is easy to compute “forwards” but difficult to compute “backwards”

Trap door function

it is fairly cheap to compute the output from the input but computationally infeasible to find the input from the output

Encryption Process

C = Me mod n

Decryption Process

M = Cd mod n

Alan Turing

Father of Computer Science

Error Detection
Error Correction

2 Goals of Coding Theory

Source coding

changing the message source to a suitable code for transmission through the channel

Source encoder

transforms the source output into a sequence of symbols or message

Codeword

a string of 0’s and 1’s representing an actual message

Length

number of digits in a codeword

Code

the collection or set of all codewords

Encode

message → codeword

Decode

received word → message

Parity

a single bit is appended to a bit string; either odd or even

Repetition

simplest possible error-correcting code

Hamming distance

number of bits where the two words differ

Nearest Neighbor Decoding

If the distance between the closest codewords in C is large enough and if sufficiently few errors were made in transmission, this codeword should be x

Minimum distance

smallest distance between any two distinct codewords in the code

2e + 1

Minimum distance

2e

Errors detected at minimum distance

e

Errors corrected at minimum distance

Product tags

used for easy identification of products as well as for tracking and inventory purposes

Universal Product Code

originally created to help grocery stores speed up the checkout process and keep better track of inventory

Check digit scheme

appends an extra digit or digits to the product tag

Check digit scheme

given the eleven-digit string x1x2 ... x11, x12 is appended such that the whole twelve-digit codeword satisfies:

3𝑥1 + 𝑥2 + 3𝑥3 + 𝑥4 + ⋯ + 3𝑥11 + 𝑥12 ≡ 0 mod 10

Quick response code

was in Japan by Denso-Wave in 1994

Quick response code

designed to allow high speed component scanning

Quick response code

detected as a 2-dimensional digital image by a semi-conductor image sensor