Welcome to Symmetric Cryptography! Symmetric cryptography relies on shared secret key to ensure message confidentiality, so that the unauthorized attackers cannot retrieve the message. The course describes substitution and transposition techniques, which were the bases for classical cryptography when the message is encoded in natural language such as English. Then, we build on product ciphers (using both substitution and transposition/permutation) to describe modern block ciphers and review the widely used cipher algorithms in DES, 3-DES, and AES. Lastly, we enable the use of block ciphers to support variable data length by introducing different modes of block cipher operations in ECB, CBC, CFB, OFB, and CTR modes. This course is cross-listed and is a part of the two specializations, the Applied Cryptography specialization and the Introduction to Applied Cryptography specialization.
Modulo Operation
Loading...
来自 University of Colorado System 的课程
Symmetric Cryptography
36 个评分
从本节课中
Classical Cipher: Substitution
This module defines substitution cipher technique and describes multiple examples for substitution-based classical algorithms: Caesar Cipher, Monoalphabetic Cipher, and Vigenere Cipher (which is a type of Polyalphabetic Cipher). We will also discuss the mathematical concepts in Modulo Operations to use them to describe the cipher algorithms.
与讲师见面
Sang-Yoon ChangAssistant Professor
Computer Science
In the previous lesson,
we discussed about how different keys,
for example, x = 25, x = -1,
x =51 and so on,
provide the same mapping for Caesar cipher when encrypting English.
These are clearly different values for keys,
but they produce equivalent Caesar cipher processes.
That is, the input output mappings are the same.
There is a rule here for the different keys that result in the same mappings.
In this case, given English which has 26 plaintexts alphabets,
x has the same remainder when dividing it by 26.
More specifically, from the example of x = 25,
all other values of x that have a remainder of 25 when
divided by 26 are equivalent to x = 25.
In this lesson, we will describe how
we can express this phenomenon mathematically using modulo operations.
Let's define the mathematical concepts and modulo operations.
Some of these concepts will overlap with arithmetic,
so you would want to think back to when you first learned
divisions, quotients, and remainder.
First, we are given a modulus n which is a positive integer.
For example, previously, the n was 26 for English letters,
then (a mod n) is the remainder when a is divided by n. In other words,
if a = q × n + r,
where q is the quotient and r is the remainder,
a mod n = r.
You may have used natural numbers,
which are positive integers when you first learned about divisions.
But, negative quotients are allowed here,
which is why x = 25 and x =
-1 were yielding the same mapping for Caesar cipher encrypting English letters.
For two different integers a and b,
if (a mod n) = (b mod n),
then a and b are said to be congruent modulo
n. And we use a symbol with three horizontal lines for the congruent's relations.
Again, there are three lines with just one more line than the equal sign in mathematics.
Let's look at an example;
12 mod 7 is 5 because 12 is equal to 7 × 1 + 5.
Similarly, -11 = 7 × (-2) + 3 and therefore -11 mod 7 is 3.
From the expression in the quotation,
using the variables a,
q, n, and r,
where it states a = q × n + r,
all of these variables a,
q, n, and r, are integers.
While the variables a, q,
and r can have any signs and be positive, negative,
or zero, the modulus n,
the variable n is given and is a positive integer or a natural number.
Given a modulus n,
there are infinite numbers that are congruent to each other,
as there are infinite number of possible integers that provide
the same remainder when divided by n. For example,
when n = 7 -9 -2, 5,
12, 19 and so on are all congruent to modulo n or modulo 7.
Mod n operator maps all integers into the set of integers between 0 and n-1.
These integers that are between zero and n-1 are called residue classes and is
denoted by z sub n. Given the integer in modulo n,
there are n residue classes from zero to n-1.
For example, when the modulus is seven,
there are seven residue classes between zero and six
and all integers can be exclusively mapped into a residue class.
The process of finding which residue class an integer belongs
to is called reducing modulo n. In other words,
given the modulus n,
reducing (a modulo n),
or reducing (a mod n),
corresponds to finding the smallest non-negative integer r
to which a is congruent to (r mod n).
Let's go back to the Caesar cipher where the key indicates the shift and alphabets.
For example, in the previous example with the key of x = 4,
this example shifted the plaintext by four alphabets.
To mathematically describe Caesar cipher,
we first to encode the alphabets,
in this case, English letters to integers.
A becomes zero, B becomes one,
C becomes two and so on until Z becomes 25.
The integers between zero and 25 are used to represent the alphabets in English letters.
After this encoding between letters to integers,
we can describe the operations of Caesar cipher in mathematics.
First, we were given the modulus 26 which is
the English alphabet size and the key with the variable x.
The encryption process of Caesar cipher is the right cyclic shift by the amount of x.
The ciphertext alphabet c is equal to the plaintext alphabet (p + x),
and then taking the sum mod 26.
The addition captures the right shift while
the modulo operation captures the cyclic operation.
Similarly, the decryption process performs
the reverse of the encryption and does a left cyclic shift;
the plaintext alphabet p can be derived from
the ciphertext alphabet c by taking c and subtracting by x mod 26.
