Roleplayer
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 process 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)


Copyright © 1997-2014 by Steve Jackson Games. All rights reserved.

Steve Jackson Games | GURPS | Roleplayer Index