Skip to content

HTTPS clone URL

Subversion checkout URL

You can clone with HTTPS or Subversion.

Download ZIP
Newer
Older
100644 50 lines (44 sloc) 2.295 kb
9e6d37e @pfranusic Added actual files to repo.
authored
1 %%%% why-RSA-works/exponential-notation.tex
2 %%%% Copyright 2012 Peter Franusic.
3 %%%% All rights reserved.
4 %%%%
5
6 Let's say we're given three elements $a,b,c$ which are members of the set $Z_n$.
7 We're also given the expression $a \otimes b \otimes c$.
8 The question is this: How do we compute this expression?
9 Do we first multiply $a$ and $b$ and then multiply $c$?
10 Or do we multiply $b$ and $c$ and then multiply $a$?
11 The answer is that either way is correct.
12 It doesn't matter what order we multiply the elements.
13 This is because the ring $\mathcal{R}_n$ has the property of \emph{multiplicative association}.
14 The multiplicative association property says that
15 when we have a series of $\otimes$ operations,
16 we can do the operations in whatever order we want.
17 The answer will be the same.
18 \begin{eqnarray*}
19 a \otimes b \otimes c &=& (a \otimes b) \otimes c \\
20 &=& a \otimes (b \otimes c)
21 \end{eqnarray*}
22
23 The modex function is represented mathematically using \emph{exponential notation}.
24 Exponential notation is an efficient way to describe a series of multiplications of the same value.
25 For example, the value $m$ can be multiplied by itself any number of times.
26 We use exponential notation to describe this.
27 Remember that it doesn't matter in what order the $m$'s are multiplied together.
28 \begin{eqnarray*}
29 \overbrace{m}^1 &=& m^1 \\
30 \overbrace{m \otimes m}^2 &=& m^2 \\
31 \overbrace{m \otimes m \otimes m}^3 &=& m^3 \\
32 \overbrace{m \otimes m \otimes m \otimes m}^4 &=& m^4 \\
33 &\vdots&
34 \end{eqnarray*}
35
36 RSA uses the exponential notation $m^e$.
37 The value $m$ is the \emph{message} integer.
38 The value $e$ is the \emph{encryptor} exponent.
39 The exponential notation $m^e$ means that $e$ copies of $m$ are multiplied together
40 using the $\otimes$ operator in the ring $\mathcal{R}_n$.
41 \[ m^e \quad = \quad \overbrace{m \otimes m \otimes m \, \cdots \otimes m \otimes m}^e \]
42
43 RSA also uses the exponential notation $c^d$.
44 The value $c$ is the \emph{ciphertext} integer.
45 The value $d$ is the \emph{decryptor} exponent.
46 The exponential notation $c^d$ means that $d$ copies of $c$ are multiplied together
47 using the $\otimes$ operator in the ring $\mathcal{R}_n$.
48 \[ c^d \quad = \quad \overbrace{c \otimes c \otimes c \, \cdots \otimes c \otimes c}^d \]
49
Something went wrong with that request. Please try again.