Roleplayer #28, April 1992
Public Key Encryption
Cryptography for Everyone
by Sean Barrett
Secret messages are an integral part of many adventure scenarios. Whether
the campaign is GURPS
Cyberpunk, Illuminati,
Special Ops,
Espionage
or far-future
adventure, sending -- or breaking -- confidential messages can be an important
plot element.
Those wishing to send confidential messages obviously must devise a scheme
to discourage unauthorized reading. That is only the first problem, though.
Once a system is developed, the parties must somehow communicate the cryptosystem
and keys to each other. If they can meet, this is not difficult . . . but
how can Feliks, somewhere in Moscow, establish secure communications with
Miaojin, somewhere in Beijing, when neither of them can leave their countries?
In late TL7 several public-key cryptosystems to allow exactly that become
public record. As of this writing, everything described here has been widely
available and in actual use for several years.
The RSA Cryptosystem
In 1983, U.S. patent #4,405,829 was issued to MIT for the Rivest-Shamir-Adleman
public key cryptosystem. A company called Public Key Partners (PKP) holds
the exclusive commercial license to sell and sub-license the RSA public
key cryptosystem. On June 5, 1991, alarmed by the US government's increasing
monitoring of private communications, programmer Phil Zimmerman began widely
distributing, for free (and, according to PKP, illegally), the source code
for an implementation of that cryptosystem, called Pretty Good Privacy.
How long PKP's legal monopoly lasts depends on how effective their actions
against Zimmerman are. In any case, Complexity 1 public key encryption and
authentication software becomes available for all computer platforms in
late TL7.
This method of encryption requires two keys: a public and a private key.
Because of the "knapsack" mathematics of those keys, knowing one
key does not help in deducing the other. Usually, the public key is widely
published and clearly labeled: "anyone who wants to write to Feliks,
encrypt your message using this key!" Despite the fact that the public
key is available to everyone, even the bad guys, no one can read a message
encrypted by it -- unless they have the private key. The encryption key
will not decrypt the message it just encrypted!
It works the other way as well. Feliks can encrypt a message using his private
key that anyone with his public key can read. Pairs of keys can only decrypt
each other's messages, and Feliks is the only one who has his private key,
so any message readable by his public key can only be from him. When
Feliks sends a message to Miaojin, he will use both his own private key,
to authenticate it, and Miaojin's public key, so only Miaojin can read it.
Because of the very large numbers involved, public key cryptosystems cannot
be used on communications equipment unless it is computerized.
Key Management
A user of this cryptosystem must first generate a key-pair. One key of the
pair is published openly. The other is kept as secure as possible.
Each key-pair has a Crypto-Level (QL), chosen when it is created. That is
the time, in seconds, required by a Complexity 1 program to encrypt or decrypt
a one-kilobyte message with those keys. Messages may be compressed before
encryption, reducing their size to between one-half and one-quarter of their
full size. (This article, without typesetting codes, is just over 10 KB,
but can be compressed to about 4 KB.) Higher Complexity programs speed the
pro-cess exponentially, as described on p. CY62. Multiply the time by the
size of the message in kilobytes. The time required to decrypt the message
is the same if the proper key is used.
It is quite possible to generate several key-pairs of different QLs: a quick-and-unsafe
one for routine use, and a slow-and-sure one for sensitive traffic.
A typical user will accumulate many keys: his own pri-vate keys, and the
public keys of everyone he wants to communicate with. These keys are actually
very large num-bers, comprising thousands of bits. They can only be memorized
by characters with 60-point Eidetic Memory -- anyone else must
keep his keys in computer files.
Those files are the weak point of this cryptosystem, and must be protected.
The various public keys are not sensitive -- they are public, after all
-- but if a user's private key is compromised, he is in bad shape. Someone
else can now read all his mail and can send messages with his signature,
and he may not even realize it until tremendous damage has been done! A
key file may be encrypted using another, single-key, cryptosystem, but if
access to the file is gained, it can be attacked using the simple guessing
methods described in the sidebar on p. CY63. (Of course, anybody using a
guessable password deserves everything that is about to happen to him .
. .)
Use, Authorized and Un-
Since all modern cryptosystems are computer driven, only a routine Computer
Operations Skill roll is necessary to encrypt or decrypt a message if the
key is known. Most messages will have a plaintext "tag" identifying
the sender, so the computer even selects the proper key to use.
Breaking an encrypted message is also computer-intensive. Since
keys are computer-generated, guesses based on relatives' names and such
are useless; the encryption must be attacked mathematically. After the Computer
Operations roll to run the cracking program, the Cryptanalysis skill of
the program is used rather than that of the operator. Once a message has
been cracked, that key-pair is known. All further messages using either
of those keys can be simply decrypted and read.
If the public key that was used to encrypt the message being attacked is
available (the usual situation), a roll is made against the program's skill
level, minus the number of digits in the encryption key's QL. A critical
failure indicates that this program can never decrypt this message. Barring
that, multiple attempts are possible, but the time required for each roll
is the encrypting key's QL, in days! Again, higher Complexity programs
speed the process.
If the encryption key is unavailable for some reason, cracking is much
harder -- at TL7, it is believed impossible. At higher TLs, the GM may decide
to allow an attempt. The Cryptanalysis roll should suffer a large penalty,
and the time required should be long -- based on a time in the decades
on TL7 Complexity 4 computers.
The attacker usually will not know the QL of the key that was used to encrypt
the message he has intercepted. The GM should make all rolls in secret and
tell the attacker only when he succeeds.
For example, Feliks needs to send a 2 KB message to Miaojin. He uses his
Complexity 4 workstation, with Miaojin's routine public key of QL 10,000.
It will take two seconds to encrypt the message. Miaojin, operating a Complexity
3 laptop, will need 20 seconds to read it. Meanwhile, the bad guys intercept
the message and set about cracking it with their Complexity 5, Cryptanalysis-20
mainframe program. If they have Miaojin's public key, they will roll against
an effective skill of 15 every 144 minutes (one-tenth of a day).
If the message were important, Feliks could have used Miaojin's sensitive
key (QL 300,000) and taken a full minute to encrypt the message. Miaojin
would need ten minutes to read it, but the bad guys would roll against an
effective skill of 14, at three days per roll! The message will
probably be obsolete by the time they can read it. Of course, Miaojin will
need to change his key, because having cracked it once, they know it.
A character may write his own cryptanalytic program using the standard procedure;
if the Programming roll is successful, such a program has the writer's Cryptanalysis
Skill -2. If the roll was a critical success, it has his Skill at no penalty.
Cryptography programs are at least Complexity 3.
Legality
Effective cryptosystems are of Legality 2 or lower. Legal cryptosystems
usually have "back doors" built in so that intelligence agencies
can easily monitor the traffic. On April 17, 1991, the New York Times
reported on a Senate proposal stating ". . . providers of electronic
communications services and manufacturers of electronic communications service
equipment shall insure that communications systems permit the Government
to obtain the plain text contents of voice, data, and other communications
. . . ." In some countries, simply transmitting an encrypted message,
regardless of content, is prima facie evidence of treason.
Authentication
A related subject to encryption is authentication: how can I be sure that
no one has tampered with this message? One answer is a message digest. It
is like a checksum in that it compactly "represents" the message
and is used to detect changes in the message. However, it is computationally
unfeasible, at least at current tech levels, to devise a substitute message
that would produce an identical digest.
A document can be electronically "signed" by encrypting its digest
with a private key. Anyone can check such a "signature" by using
the signer's public key to decrypt it, thus proving the identity of the
signer and that the document has not been subsequently altered.
Forgery of a signature is unfeasible and the signer cannot later disavow
his signature.
Oblivious Transfer
A variant of public-key encryption can be used to perform "oblivious
transfers" in which there is a less-than-certain chance that a message
can be decrypted by the receiver. The sender will not know if the receiver
can read it. This scheme creates "plausible deniability": if a
message is sent to many people, but there is only a chance that any single
person could actually read it, then it is impossible to prove who actually
received the information.
To make such a transfer, a notice containing a random number is sent to
each receiver. The receiver encrypts the notice with his private key, and
returns it to the sender. The sender now encrypts the actual message using
the returned notice and the original random number in a special algorithm,
and sends it to the receiver. Any of these three message transfers may be
public. The final message may be cryptanalytically attacked exactly as described
as above.
That special algorithm is designed so that there is a fixed chance, for
instance 5 in 6, that the receiver s private key will be able to decrypt
the message. Since the sender cannot determine the receiver's private key,
there is no record anywhere of whether or not the receiver was able to read
the message. If the receiver keeps his key secret, and destroys the message
after his decryption attempt, he can then deny ever reading it, and it is
impossible to determine whether he is lying.
Uses of this technique are left as an exercise for the <fnord>.
(Back to Roleplayer
#28 Table of Contents)