rsa/groupProjectProposal.tex at master · adelman/rsa · GitHub

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55
56
57
58
59
60
61
62
63
64
65
66
67
68
69
70
71
72
73
74
75
76
77
78
79
80
81
82
83
84
85
86
87
88
89
90
91
92
93
94
95
96
97
98
99
100
101
102
103
104
105
106
107
108
109
110
111
112
113
114
115
116
117
118
119
120
121
122
123
124
125
126
127
128
129
130
131
132
133
134
135
136
137
\documentclass[12pt]{article}

\title{COMP 360 Group Project:\\RSA Implementation and Exploration}
\author{Matt Adelman, Evan Carmi, Adam Forbes}
\date{\today}

\usepackage{amsmath}
\usepackage{amssymb}
\usepackage{amsfonts}
\usepackage{amsthm}
\usepackage{enumerate}
\usepackage{graphicx}
\usepackage{subfig}
\usepackage{lscape}
\usepackage{pdflscape}
\usepackage[utf8]{inputenc}


\usepackage[margin=1in]{geometry}

\usepackage{fancyhdr}
\pagestyle{fancy}
\lhead{}
\chead{}
\rhead{COMP 360: Matt Adelman, Evan Carmi, Adam Forbes}
\lfoot{}
\cfoot{\thepage}
\rfoot{}

\let\cat\frown
\def\evalto{\mathord{\;\downarrow\;}}
\def\notdefined{\mathord{\uparrow}}
\let\parto\rightharpoonup
\let\vdash\proves
\def\vlist{$[v]$}
\def\Gp{\Gamma\proves}
\def\Gpp{\Gamma'\proves}
\def\Gppp{\Gamma''\proves}
\def\fp{\textbf{FUN$+$}}
\newcommand{\ty}[1]{\texttt{#1}}
\def\nil{\ty{nil }}
\newcommand{\rz}{\ty{raise }exn}
\newcommand{\hndl}[2]{#1\ty{ handle } exn => #2}
\newcommand{\ttt}[1]{\texttt{#1}}
\newcommand{\insertt}{\texttt{insert}}
\newcommand{\insertp}{\texttt{insert'}}
\newcommand{\wbl}{weight-biased leftist }


\def\setseparator{\mid}
\newcommand{\set}[2][\relax]{
  \ifx#1\relax
    \{#2\}
  \else
    \ifx#1\left
      \left\{#2\right\}
    \else
      \csname #1l\endcsname\{#2\csname #1r\endcsname\}
    \fi
  \fi
}
\newcommand{\keys}{\text{keys}}
\newcommand{\rank}{\text{rank }}
\newcommand{\setst}[3][\relax]{\set[#1]{#2\setseparator#3}}
\newcommand{\setidx}[3][\relax]{\set[#1]{#2}_{{#3}}}

\begin{document}
\maketitle

\paragraph{Brief History:\\}
RSA is a public key encryption algorithm developed by Ron Rivest, Adi Shamir,
and Leonard Adleman at MIT in 1977. Rivest and Shamir are both computer
scientists that were working on an ``unbreakable'' public key encryption method.
Rivest and Shamir worked on many different codes, and would pose them as a
challenge to Adleman. Forty two of these codes were presented, and Adleman broke
them all. Finally on attempty number 43, they created what is now known as the
RSA scheme. Incidentally, English Professor CLifford Cocks developed the exact
same encryption system in 1973, but it was classified as top-secret, so it was
not released until 1997. The RSA algorithm was released for public domain in
1997.\\\indent
The algorithm operates by using two distinct, large prime numbers to generate
public and private keys. Anyone can use the public key to encrypt a message, but
only someone with the private key can decrypt it. The algorithm is hard to
break, because if the prime numbers are large enough, the factorization is
exponential in time.

\paragraph{Implementation:\\}
To further explore the RSA algorithm and the difficulties in an actual
implementation we will write the algorithm in JavaScript, embedded in a web
page. There has been some research done on web based implementations and
(http://www-cs-students.stanford.edu/~tjw/jsbn/) may serve as a resource.
Additionally, we will explore possible speed improvements, such as Chinese
remainder theorem, and error checking. If possible, providing a visualization
of the process would also be a goal of ours. In terms of difficulty
implementation the algorithm shouldn't be too difficult, although further
improvements and a clean interface may provide interesting challenges. Ideally
we wouldn't simply replicate previous JavaScript implementation's of RSA,
rather creating a new, clean, fast and explicative version which would provide
the base of further experimentation.

\paragraph{Common Implementation Flaws:\\}
Because the security implications of an improperly implemented RSA algorithm
are so dire we would like to include within the scope of our project common
mistakes made throughout the industry. These aren’t trivial mistakes by any means,
but rather exploitations of the properties of prime numbers, poor random and
pseudorandom choices leading to weak seeds, selecting seeds of low entropy,
generating keys using the same factor, and other implementation flaws. A full
understanding of the most common implementation mistakes is essential in crafting
a strong algorithm that is up to contemporary cryptographic standards. Therefore
we’d like to include this research as it not only serves as an interesting area
of exploration in decryption, but also proves the strength of our algorithm.


\paragraph{Final Notes:\\}
Additionally, we have all expressed interested in having this project serve as
a example to show on our résumé or CV. To that end, having a project written in
JavaScript, that runs in a web browser, would be both a portable and easily
presentable choice of tools.

\paragraph{Our List of primary references is as follows:\\}
http://en.wikipedia.org/wiki/RSA\_(algorithm)\\
http://www-cs-students.stanford.edu/~tjw/jsbn/

\end{document}

%%%%%%%%%% Points we wanted to include %%%%%%%%%%

1) History\\
2) Make our own implementation\\
3) Visualization\\
4) Common implementation flaws\\
5) Fixes for these flaws\\

Main Goals:\\
1) Implementation\\
2) Visualization\\
3) ``Good Key'' checking\\