Cryptography: RSA and Factoring; DigitalSignatures; SshGreg PlaxtonTheory in Programming Practice, Spring 2005Department of Computer ScienceUniversity of Texas at AustinThe Hardness of Breaking RSA• One approach to breaking RSA is to try to compute the private key(d, n) from the public key (e, n), i.e., to compute d from e and n• No one has proven that this is the only way to break RSA, but manyexperts believe that this is the case• In what follows we will argue that the problem of computing d from eand n is essentially equivalent in difficulty to the problem of factoringn– Given the prime factors p and q of n, it is possible to compute defficiently– Given d such that de is congruent to 1 modulo φ(n), it is possibleto factor n efficientlyTheory in Programming Practice, Plaxton, Spring 2005Computation of d from e, p, and q• Note the symmetry of RSA with respect to d and e– We can switch the public/private roles of the keys (d, n) and (e, n),and the scheme still works– This property will come in handy again later when we discuss digitalsignatures• So we can compute d from e, p, and q in the same way that wepreviously computed e from d, p, and q– Use the extended Euclid algorithmTheory in Programming Practice, Plaxton, Spring 2005Computation of p and q from d, e, and n• We know that de − 1 is a multiple of φ(n), so we can easily computea multiple of φ(n)• It can be shown that given such a multiple of φ(n), n can be factoredefficiently• The proof is somewhat technical, so we content ourselves with provinga weaker result, namely, that given n and φ(n) we can compute p andq efficiently– Given n = pq and φ(n) = (p − 1)(q − 1) = n − (p + q) + 1, we caneasily compute p + q = n − φ(n) + 1– Given n = pq and p + q we can compute p − q sincep − q =p(p − q)2=p(p + q)2− 4pq– Given p − q and p + q we can easily solve for p and qTheory in Programming Practice, Plaxton, Spring 2005Digital Signatures• Desirable properties of a document intended for Bob that iselectronically signed by Alice:– Only Bob can decrypt the message, and he is convinced that it wassent by Alice– Alice cannot deny signing the document– No one can modify the document without invalidating Alice’ssignature• RSA is widely used for such digital signatures– Let’s see how this can be doneTheory in Programming Practice, Plaxton, Spring 2005Digital Signatures via RSA• Suppose Alice wants to sign a document and send it to Bob• She encrypts the document x with her private key f−1a, and thenencrypts the result with Bob’s public key fb, i.e., she sends Bobfb(f−1a(x))• Bob decrypts by applying his private key f−1b, yielding f−1a(x), followedby Alice’s public key fa, yielding x• In cases where Bob might not be sure who is sending him the document,Alice can send fb(y) where y is the concatenation of Alice’s name (inplaintext) and f−1a(x)– Note that Bob is not fooled if someone else’s name is includedinstead– If Carol’s name is concatenated to f−1a(x), Bob obtains gibberishwhen he computes fc(f−1a(x))Theory in Programming Practice, Plaxton, Spring 2005Alice Cannot Deny Sending the Message• An impartial judge can determine that Alice signed the document, sincethe only way to get anything sensible out of f−1a(x) (which can besupplied by Bob) is to apply Alice’s public key fa– This assumes that Alice is the only person who knows her privatekey– Safeguarding private keys is criticalTheory in Programming Practice, Plaxton, Spring 2005No One Can Modify Alice’s Signed Document• Suppose Bob changes one or more bits of the encrypted documentf−1a(x)• Application of Alice’s public key fathen yields gibberishTheory in Programming Practice, Plaxton, Spring 2005Ensuring Security of Communication with a TrustedThird Party• In an RSA cryptosystem, we often need to retrieve the public key ofanother party• Such keys may be obtained from a trusted third party, David, whomaintains a database of public keys• We need to be wary of an attacker Eve who might intercept a requestto David and respond with the wrong public key• Solution: David signs any public keys that he sends out– Eve can no longer pose as DavidTheory in Programming Practice, Plaxton, Spring 2005Another Application of Public Key Cryptography: Ssh• Provides a secure version of telnet• We will give a brief overview of ssh and some related tools• The ssh environment consists of a network of hosts (machines)– Each host has a unique public/private key pair– Each host runs a daemon process sshd– Users of these hosts set up certain files containing public and privatekeys in a manner to be described– Users run ssh to connect from one host to anotherTheory in Programming Practice, Plaxton, Spring 2005Ssh: Basic User Configuration• Within a user account (in the .ssh subdirectory), the following basicfiles are created/maintained– Public/private key pairs are created using ssh-keygen– Private key files should not be readable by other users; for addedsecurity, private key files are often encrypted using a passphrase– An “authorized keys” file, maintained by the user, that contains alist of public keys such that the holder of any associated private keyis authorized to connect to this account– A “known hosts” file, maintained by ssh (but editable), that containsthe “verified” public keys of the hosts to which this user has previouslyconnectedTheory in Programming Practice, Plaxton, Spring 2005Using Ssh: The Basics• To (attempt to) connect to another account, run “ssh user@host”• If no private key is specified on the command line, a default privatekey file is assumed; if the private key is passphrase-protected, the useris prompted for the passphrase• If the public key of the target host does not appear in the known hostsfile, then the public key of the target host is displayed, and the user isasked whether to accept it– If the public key of the remote host is accepted, it is added to theknown hosts file– In high-security environments, a user might telephone someone todecide whether to accept a given host public key• The attempt to connect succeeds if the associated public key resides inthe authorized keys file of the target account• If not, the user is prompted for the account passwordTheory in Programming Practice, Plaxton, Spring 2005Ssh: The scp Command• The scp command is like the unix cp command, but it can be used