Pontifex is the codename for a fictional (but none the less effective) cryptosystem, mentioned in Neal Stephenson's novel Cryptonomicon, nominated for the 2000 Hugo Award.
In the novel, Pontifex was the brainchild of the character Enoch Root, a World War II veteran, Catholic Priest and member of the mysterious Societas Eruditorum. Pontifex is a simple algorithm, harking back (as one might expect) to late-WW2 cryptosystems. In reality, the system is known as Solitaire, and was developed by the cryptographer Bruce Schneier. The function of the Pontifex algorithm is to produce a series of pseudo-random numbers known as a keystream. This series is then combined with the true message in the fashion of a one-time pad, producing encrypted cyphertext. For those who are not aware, an ideal one-time pad is the only truly unbreakable cryptosystem, in which each character bears absolutely no relation to any other in the keystream. In practice this is very difficult to accomplish even with 'random' elements like humans, much less algorithms.
In the family of cryptosystems, Pontifex is known as an n-element permutation. This system is very similar to RC4, which by today's standards is a weak algorithm. Such algorithms are considered weak because they are essentially single-rotor systems. Although the rotor (or permutation) evolves during it's generation, it is not as strong as modern prime-factor and discrete-logarithm systems such as AES and PGP. Pontifex uses a 54-element permutation algorithm, which it uses as its key. Only one key is used per message, if this rule is broken the integrity of the system is compromised. This permutation is then used to generate the keystream, which is then added in modulo-26 arithmetic to the plaintext. The process of generating each character in the keystream alters the permutation, in a reversible but mostly random fashion.
The following is the Pontifex algorithm, written as a Perl script. This algorithm can run on any UNIX variant equipped with the Perl scripting language.
#!/usr/bin/perl -s
$f=$d?-1 : 1;
$D=pack('C*'.33..86);
$p=shift;
$p=~y/a-z/A-Z/;
$U='$D=~s/(.*)U$/U$1/;
$D=~s/U(.)/S1U/;';($V=$U)=~s/U/V/g;
$p=~s/[A-Z]/$k=ord($&)-64,&e/eg;
$k=0;
while(< >)
{
y/a-z/A-Z/;
y/A-Z//dc;
$o.=$_
}
$o.='X'
while length ($o)%5&&!$d;
$o=~s/./chr(($f*&e+ord($&)-13)%26+65)/eg;
$o=~s/X*$// if $d;
$o=~s/.{5}/$& /g;
print"$o\n";
sub v
{
$v=ord(substr($D,$_[0]))-32;
$v>52?52 : $v
}
sub w
{
$D=~s/(.{$_[0&93;)(.*)(.)/$2$1$3/
}
sub e
{
eval"$U$V$V";
$D=~s/(.*)([UV].*[UV])(.*)/$3$2$1/;
&w(&v(53));
$k?(&w(&k)) : ($c=&v(&v(0)),$c>52?&e : $c)
}
This script composes the Pontifex Transform. The variable $D contains the 54-element permutation; the subroutine e generates the next character in the keystream whilst performing the evolutionary operation on $D. This code is written out here exactly as it is in the book, for the sake of accuracy. If you wish to understand it more clearly, I suggest the use of a PERL beautifier like pb.
It is notable that Pontifex uses a 54-element permutation. The Pontifex Transform would work mathematically with any number, hence n-element permutation. Generally, today's cryptosystems operate in terms of 256-element permutations, with greatly increased resistance to cryptanalysis. Herein lies Pontifex's greatest strength - it requires no computers, rotor machines or calculators to operate. All that is required to encrypt and decrypt with Pontifex is a deck of cards. Hence the 54-element permutation. In terms of pure number theory, a deck of cards is just a set of entities, their order constituting a 54-element permutation. By correctly manipulating a normal deck of cards, you can encrypt any message you choose and rely on it being decrypted by the recipient, as long as nobody shuffles the deck in the meantime.
In modern terms, Pontifex is weak. A modern personal computer with a few cryptanalysis routines programmed into it could easily break any message. However, the question must be asked, if two prisoners are playing cards in a shared cell, would anyone really think to check the deck they were using?