12345678910111213141516171819202122232425262728293031323334353637383940414243444546474849505152535455565758596061626364656667686970717273747576777879808182 
 \documentclass{article}

 \usepackage{amsmath}
 \usepackage{amsfonts}

 \title{Oracle Attacks on Various Cryptosystems}
 \author{Josh Gordon, Thomas Johnson, Anthony Mangiacapra}
 \date{\today}

 \begin{document}

 \maketitle

 \section{Abstract}
 Many cryptosystems rely on ``blackmail'' proofs that they are difficult to break, such as reducing RSA to factoring, or GoldwasserMicali to testing for quadratic residues. In this report, we highlight several instances of this blackmailing, and explore the consequences of breaking some assumptions about hardness made when discussing the security of these systems.

 \clearpage
 \newpage

 \section{Introduction}
 The object of study for this paper is the \textbf{oracle}. The idea is to take some problem (ideally one we don't have a good solution for) and pretend we have a good solution for it, call that solution an oracle, and then figure out what we can solve using it.

 A common example is a halting oracle; a box that takes in an instance of the halting problem and outputs the correct answer every time. We conveniently ignore the prospect of constructing a paradox when working with this box.

 \section{Results}
 \subsection{Order Finding}
 The first oracle we consider is for the following problem: Given a group $G$ and an element $a \in G$, compute the \textbf{order} of $a$. This is the smallest positive integer $r$ such that $a^r = e$ where $e$ is the identity element of $G$. Unlike other oracles to be considered later, this one currently does have an implemented analog: the quantum part of Shor's factoring algorithm. Using this oracle, we show how to decrypt an intercepted RSA transmission:

 \begin{verbatim}
 Given: RSA modulus N, encryption exponent e, message ciphertext c
 1. Choose a random integer a between 1 and N
 2. Let g = gcd(a,N)
 3. if g != 1, then a is either p or q and goto step 8
 4. Apply the oracle to find r, the order of a in Z/ZN
 5. If r is odd, goto step 1
 6. if pow(a,r/2,N) = 1, goto step 1
 7. Compute pow(a,r/2,N) + 1 and pow(a,r/2,N)  1. One of these is p or q.
 8. With the known prime, divide N to get the other prime. p and q are now known.
 9. Compute phi = (p1)(q1)
 10.Use the pulverizer to find d, the inverse of e mod phi.
 11.Compute pow(c,d,N) as the message plaintext.
 \end{verbatim}

 A similar algorithm can be used to break vanilla Elgamal, first factoring and then following the key generation process to acquire the decryption key.

 \subsection{Halting Oracle}
 Unlike the order finding oracle, no one has been able to build a halting oracle, quantum or not. In fact, no one can build a halting oracle, but that is beside the point for the discussion of the consequences. Our halting oracle solves the following problem: Given an encoding of a turing machine $\langle M \rangle$ and an input $w$, return true if $M$ halts on $w$, and false otherwise.

 This oracle is extremely powerful, but nevertheless interesting as not having a direct connection to number theory or algebra such as the order finding oracle. We will use the oracle to decrypt an RSA ciphertext $c$ with keys $N,e$.

 For a string $w$, we define a Turing machine $T$ that operates as such: With $w$ on the tape, encrypt it using the public keys. If the encrypted version is equivalent to $c$, halt. Otherwise, write the lexicographically next string from $w$ on the tape and repeat.

 We can now binary search on strings of a specific length by checking whether $T$ halts on any given string in the space. If we have a message that is $k$ bits long, we have $2^k$ strings to search. By checking if $T$ halts on any given string in this space, we can tell if the plaintext comes before or after it lexicographically.

 Taking the requisite $O(\log(k))$ searches on $2^k$ strings, we have an algorithm to find the plaintext that encrypts to a given ciphertext in linear time.

 It should be noted that this generalizes beyond RSA; this algorithm can decrypt any ciphertext encrypted in a deterministic public key cryptosystem.

 \subsection{SAT Oracle}
 The SAT oracle solves the following problem: Given a boolean formula of propositional logic in terms of literals and variables, return true if there exists an assignment to the variables that causes the formula to evaluate to true, and false otherwise.

 We will take a similar approach to how we used the halting oracle, and define a function on strings that allows us to binary search for a plaintext that encrypts to a given ciphertext.

 Where we used the halting oracle to tell if a runaway Turing machine would hit the ciphertext, we will use the SAT oracle to tell if a formula that affirms the existence of the ciphertext in a certain subset of the message space is satisfiable.

 First, we encode $k$bit numbers and arithmetic in propositional logic.
 The number $b_0b_1b_2...b_k$ is represented as $k$ boolean variables, each representing one bit.
 Furthermore, we can define relations such as \begin{verbatim}ADD(x,y,z),MULT(x,y,z)\end{verbatim} that are true when $x+y=z$ or $xy=z$, along with other arithmetic operations implemented as lookup tables if need be. It should be noted that $x,y,$ and $z$ are each $k$ variables.

 \noindent Ultimately, what we want to motivate is possible is a proposition \begin{verbatim}EncryptsToC(b1,b2,...,bk)\end{verbatim} that takes in $k$ bits and is true if the bitstring of the variables encrypts to a ciphertext $c$.

 The second bit of machinery we need is, given a string $w$, a relation \begin{verbatim}
 LexicographicallyAfterW(b1,b2,...,bk)
 \end{verbatim}
 which is true when the string $b$ is lexicographically after $w$. This can be implemented by a lookup table as well; runtime is the oracle's problem.

 At last, consider, given some pivot string $w$ in the $2^k$ space of strings, the formula:
 \begin{verbatim}
 EncryptsToC(X) && LexicographicallyAfterW(X)
 \end{verbatim}
 Applying the SAT oracle to this sentence will tell us if there is a bitstring in the upper half of the search space that is the desired plaintext string. We can run binary search using this, and acquire the desired plaintext in linear time.
 \end{document}
