Countries A and B have signed a nuclear test ban treaty. Now each wants to make sure the other doesn’t test any bombs. How, for example, is country A going to use seismic data to monitor country B? Country A wants to put sensors in B, which then send data back to A. Two problems arise.

1. Country A wants to be sure that Country B doesn’t modify the data.

2. Country B wants to look at the message before it’s sent to be sure that nothing else, such as espionage data, is being transmitted.

These seemingly contradictory requirements can be met by reversing RSA. First, A chooses $n=pq$ to be the product of two large primes and chooses encryption and decryption exponents $e$ and $d$. The numbers $n$ and $e$ are given to B, but $p$, $q$, and $d$ are kept secret. The sensor (it’s buried deep in the ground and is assumed to be tamper proof) collects the data $x$ and uses $d$ to encrypt $x$ to $y\equiv x^d(\text{mod}n)$. Both $x$ and $y$ are sent first to country $B$, which checks that $y^e\equiv x(\text{mod}n)$. If so, it knows that the encrypted message $y$ corresponds to the data $x$, and forwards the pair $x$, $y$ to A. Country A then checks that $y^e\equiv x(\text{mod}n)$, also. If so, A can be sure that the number $x$ has not been modified, since if $x$ is chosen, then solving $y^e\equiv x(\text{mod}n)$ for $y$ is the same as decrypting the RSA message $x$, and this is believed to be hard to do. Of course, B could choose a number $y$ first, then let $x\equiv y^e(\text{mod}n)$, but then $x$ would probably not be a meaningful message, so A would realize that something had been changed.

The preceding method is essentially the RSA signature scheme, which will be studied in Section 13.1.