9. PATIENT IDENTIFICATION, ENCRYPTION, HIPAA.
There are two, distinct problems in keeping
patient records confidential, so-called (inadvertent)
COMPUTATIONAL DISCLOSURE.
One is to encrypt specific patient identifiers,
such as name, birthdate, home address, social security number, etc.
The other is to conceal enough information
in the patient's detailed medical record
that the patient's identity may not be revealed BY INFERENCE.
There are a flurry of new regulations guiding the
use of patient records for exchange between institutions,
or for research purposes. These regulations are a
response to the rising traffic in electronic medical records,
and the corresponding real likelihood of accidental disclosure.
Examples abound in the popular media:
(1) Closure of Johns Hopkins research for a week
after discovery of irregularities in patient consent forms,
following the death of a healthy patient in a research study.
(2) A British nurse whose psychiatric history was disclosed
in a journal article, through a detailed publication
of her medical history.
(3) A banker who foreclosed on outstanding loans of all his
customers whom he knew had cancer, based upon a list
he obtained as a hospital trustee.
Understanding DATA ENCRYPTION
has experienced a new urgency among medical professionals,
on the basis of several recent developments.
First, there has been an explosive growth
in the exchange of electronic medical information,
often without careful consideration of the consequences to patient privacy.
Second, the public's response to this fear of disclosure
of their private medical information has been the introduction
of new legislation attached to the
HEALTH INFORMATION PORTABILITY AND ACCOUNTABILITY ACT (HIPAA)
also known as the KENNEDY-KASSEBAUM BILL.
It is clear that clinical-medical laboratory professionals
must be aware of these advances, if for no other reason
than to approve and contribute to the
purchase of software and security systems.
In CLASSICAL CRYPTOGRAPHY,
there is a MESSAGE, a SENDER, and a RECEIVER.
It is assumed that any communication between sender and receiver
may be easily read by a hostile person, or ATTACKER.
The usual objective of cryptography is to encode the sender's message
in such a way that the attacker cannot understand it.
In more complex cryptographic models, methods are used to authenticate
the identity of the sender, to prevent the attacker from altering
the message unbeknownst to the receiver, and to prevent the sender
from later denying that he/she sent a particular message
on a particular date and time.
The following book is an absolutely fabulous introduction
to cryptography, which can profitably be read by amateurs
and professionals alike:
Schneier B.
Applied Cryptography, Second Edition.
Protocols, Algorithms, and Source Code in C.
New York: John Wiley & Sons, 1996.
ISBN: 0-471-11709-9, 758 pages.
ENCRYPTION. The initial message prepared by the sender
is written as PLAINTEXT, which the sender converts into
CIPHERTEXT before the message
is transmitted. The process of converting plaintext into ciphertext
is called ENCRYPTION. The encryption process requires
an ENCRYPTION ALGORITHM and a KEY.
the process of recovering plaintext from ciphertext
is called DECRYPTION.
In classical cryptography, the key is exchanged secretly
between sender and receiver over secured communication,
or through a trusted intermediary.
The accepted view among professional cryptographers it that
the encryption algorithm should be published, whereas the key must
be kept secret. The purpose of publishing the encryption algorithm
is to place it before the academic cryptography community,
which will discover its flaws.
Better that the flaws in the encryption algorithm be first discovered
in academia than when the message is secretly decoded by the attacker.
SAMPLE ENCRYPTION CALCULATION.
Both the initial plaintext and the resulting ciphertext
may contain words or numbers or both, but is ultimately
convertible into a sequence of numerals, which can be processed
by computer and distributed through public communications,
including the Internet.
For simplicity of discussion, we can speak of an initial plaintext
expressed as a sequence of decimal numerals. For example,
let the letters of the alphabet be represented as two-digit
numbers from A=00 to Z=25 (ignore blank-spaces for now).
Then the plaintext for THE QUICK BROWN FOX becomes numeralized as
19070416200802100117142213051423, as follows:
THEQUICKBROWNFOX
T H E Q U I C K B R O W N F O X
19 07 04 16 20 08 02 10 01 17 14 22 13 05 14 23
Analogously, we may form a simple key consisting, say, of the
consecutive letters of the alphabet:
ABCDEFGHIJKLMNOPQRSTUVWXYZABCD....
ABCDEFGHIJKLMNOPQRS
A B C D E F G H I J K L M N O P Q R S T U....
00 01 02 03 04 05 06 07 08 09 10 11 12 13 14 15 16 17 18 19 20....
A simple encryption algorithm might consist of adding the plaintext
to the encryption-key, using
MODULO-26 ARITHMETIC.
That is, if the sum of any
two numbers obtained by ordinary addition is 26 or greater,
then you subtract 26 from the ordinary sum to obtain the modulo-26 sum.
Thus, 05+12=17 by both ordinary and modulo-26 arithmetic,
but 15+12=27 by ordinary arithmetic but 15+12=01 by modulo-26 arithmetic.
Hence, the ciphertext for THEQUICKBROWNFOX is
19080619241308170901240725180212, as follows:
19 07 04 16 20 08 02 10 01 17 14 22 13 05 14 23
(+) 00 01 02 03 04 05 06 07 08 09 10 11 12 13 14 15 (modulo-26)
_____________________________________________________
19 08 06 19 24 13 08 17 09 01 24 07 25 18 02 12
The ciphertext may then be decrypted by the receiver,
using the decryption-key AZYXWVUTSRQPONMLKJIHGFEDCBAZYX...
and modulo-26 arithmetic, as follows:
19 08 06 19 24 13 08 17 09 01 24 07 25 18 02 12
(+) 00 25 24 23 22 21 20 19 18 17 16 15 14 13 12 11 (modulo-26)
_____________________________________________________
19 07 04 16 20 08 02 10 01 17 14 22 13 05 14 23
The ONE-TIME PAD is a nearly-perfect
METHOD OF ENCRYPTION,
invented in 1917 by Major Joseph Mauborgne and Gilbert Vernam.
The method is also known as the SECRET LOOKUP TABLE
among clinical laboratory specialists, and is the only method of encryption
sanctioned by the U. S.
HEALTH INFORMATION PORTABILITY AND ACCOUNTABILITY ACT (HIPAA)
(2001, as amended).
In this method, the sender and receiver agree upon a common secret text,
which forms the key. Each key letter is used exactly once,
and then discarded forever. Ideally, the key should be completely random.
For example, if the receiver and sender employ the text
for George Orwell's 1984 as their one-time pad,
then the encryption-key becomes:
ITWASABRIGHTCOLDDAYINAPRILANDTHECLOCKSWERESTRIKINGTHIRTEENWINSTON....
Analogously, the decryption-key becomes:
SHEAIAZJSUTHYMPXXACSNALJSPANXHTWYPMYQIEWJW
Encryption of the plaintext, THEQUICKBROWNFOX, yields the ciphertext,
BAAQMIDCJXFPPTZA, as follows:
THEQUICKBROWNFOX
(+) ITWASABRIGHTCOLD
_______________________
BAAQMIDCJXFPPTZA
that is:
19 07 04 16 20 08 02 10 01 17 14 22 13 05 14 23 (plaintext)
(+) 08 19 22 00 18 00 01 17 08 06 07 19 02 14 11 03 (encryption-key)
_____________________________________________________
01 00 00 16 12 08 03 01 09 23 21 15 15 19 25 00 (ciphertext)
B A A Q M I D B J X V P P T Z A
Decryption of the ciphertext, BAAQMIDBJXVPPTZA, returns the plaintext,
THEQUICKBROWNFOX, as follows:
BAAQMIDBJXVPPTZA
(+) SHEAIAZJSUTHYMPX
_______________________
THEQUICKBROWNFOX
that is:
01 00 00 16 12 08 03 01 09 23 21 15 15 19 25 00 (ciphertext)
(+) 18 07 04 00 08 00 25 09 18 20 19 07 24 12 15 23 (decryption-key)
_____________________________________________________
19 07 04 16 20 08 02 10 01 17 14 22 13 05 14 23 (plaintext)
The next message between sender and receiver begins with the key,
DAYINAPRILANDTHECLOCKSWERESTRIKINGTHIRTEENWINSTONSMITHHISCHINNUZZLED....
The one-time-pad has the advantage of simplicity and relative security,
but it requires the maintenance of a large key, which sender and receiver
must maintain in synchrony.
The U. S. DATA ENCRYPTION STANDARD (USDES),
equivalent to the DATA ENCRYPTION ALGORITHM (DEA)
of the AMERICAN NATIONAL STANDARDS INSTITUTE (ANSI),
and DEA-1 of the
INTERNATIONAL STANDARDS ORGANIZATION (ISO),
has been a worldwide standard for data encryption for over
two decades. In the May 15, 1973, U. S. Federal Register, the
U. S. NATIONAL INSTITUTE FOR STANDARDS AND TECHNOLOGY (NIST, formerly
U. S. NATIONAL BUREAU OF STANDARDS), issued a public request for
a data encryption algorithm, which ultimately evolved into USDES.
In USDES, the plaintext is converted into a sequence of bits (0s and 1s),
in blocks of 64 bits apiece, padded with trailing 0s in case the message
is not an even multiple of 64.
For example, in the Latin-1 character set for the
AMERICAN STANDARD CODE FOR INFORMATION INTERCHANGE (ASCII),
which is the International Standards Organization (ISO)
standard ....., an 8-bit-sequence,
in which 00100001 is A, 00100010 is B, 00100011 is C,
00010000 is blank-space, 00010001 is !, etc.
In USDES, a 64-bit block, corresponding to plaintext,
is entered into the algorithm, and a corresponding 64-bit block,
corresponding to ciphertext, is returned by the algorithm.
The same algorithm and key are used for both encryption and decryption,
with minor changes. The key length is 56 bits.
The key is expressed as a 64-bit number,
but every eighth bit is an internal arithmetic check,
and not used by the encryption algorithm.
The algorithm is completely public.
All security resides within the key.
Until year 2000, security keys beyond 56 bits were illegal in the USA.
An exporter of software for large security keys
risked prosecution under the same laws as exporters
of U. S. nuclear weapons. Philip K. Zimmermann,
the author of PRETTY GOOD PRIVACY,
fought a valiant legal battle to publicize the ridiculousness
of this law, whereby U. S. commercial secrets could be easily broken into
by our sophisticated foreign competitors, but not vice versa.
Fortunately, this legal loophole has been corrected.
After initial permutation of the plaintext, the block is broken
into a left and right half, 32 bits apiece. Then there are 16 rounds
of identical operations, in which data are combined within the key.
The resulting right and left halves are joined, and a final permutation
concludes the calculation. The patent belongs to IBM.
Nowadays, various implementations of USDES are in widespread use,
including as a built-in function in PERL.
(However, I tried to use this on my free, public-domain version
of PERL, and I got back a paranoid message. Apparently, the
author of this version did not wish to risk imprisonment in
U. S. Federal prisons.)
In USDES, the plaintext is converted into a sequence of bits (0s and 1s),
in blocks of 64 bits apiece, padded with trailing 0s in case the message
is not an even multiple of 64.
A 64-bit block of plaintext enters USDES, and a 64-bit block of ciphertext
is returned by the algorithm. The same algorithm and key are used
for both encryption and decryption, with minor changes.
The key length is 56 bits. (The key is expressed as a 64-bit number,
but every eighth bit is an internal arithmetic (parity) check,
and not actually used by the encryption algorithm.)
The algorithm is completely public.
All security resides within the key.
In USDES, the two fundamental component operations are
PERMUTATION and EXCLUSIVE-OR.
In a permutation step, the order of the bits in the 64-bit sequence
is rearranged, an operation which is easily reversed.
In an exclusive-or step, denoted ^ in PERL,
each bit is subject to the operation x ^ y = z,
where z=1 if x=1 or y=1 but not both;
whereas z=0 if both (x=0 and y=0) or both (x=1 and y=1).
For example:
1011001110000101010110110011100001010101101100111000010101010101
^ 1111100001010001010111111000010100010101111110000101000101010101
______________________________________________________________________
0100101111010100000001001011110101000000010010111101010000000000
The exclusive-or operation is likewise easily reversed.
That is, if t is the plaintext, k is the key, c is the ciphertext, and
t ^ k = c, then c ^ k = t.
Both permutation and exclusive-or operations
have the desirable mathematical properties that:
(1) the ciphertext is exactly the same size as the plaintext; and
(2) each of these operations is easily reversed.
The USDES consists of a complex sequence of permutations and exclusive-ors.
BLOWFISH ENCRYPTION
was invented by Bruce Schneier in 1993,
who published the source code, and released the algorithm into the
public domain. There are no restrictions on the use or
distribution of Blowfish. After a four years of intensive testing
in the public arena, Blowfish's only known fault
is that there are some weak keys.
Blowfish is present in dozens of commercial products
including Symantec's Norton
YOUR EYES ONLY
and McAfee's
PCCRYPTO.
Symantec and McAfee are the two leading vendors
of computer-virus protection software.
DESIGN FEATURES OF BLOWFISH ENCRYPTION.
The algorithm is USDES-like, but much faster and easier to understand
and to implement on small computers.
The algorithm is so simple
that it could be explained to an undergraduate mathematics major.
The algorithm can be written in PERL and/or JavaScript,
both of which are relatively simple programming languages.
The algorithm does not use large-integer arithmetic.
Blowfish was constructed to meet the following design criteria.
1. Fast.
2. Compact.
3. Simple.
4. Variably Secure.
Blowfish is optimized for applications
in which the key does not change often.
It is significantly faster than USDES when
implemented on a 32-bit microprocessor with large data caches,
such as the Pentium.
Blowfish is a 64-bit-block algorithm with a variable-length key.
The algorithm consists to two parts:
1. KEY EXPANSION converts a key of up to 448 bytes
into several subkey 32-bit arrays: the permutation-array,
denoted Pi (i=1,...18);
and the string-array,
denoted Si,j (i=1,...4) and (j=0,...255).
2. DATA ENCRYPTION consists of a
FEISTEL FUNCTION, F(), iterated for 16 rounds.
To encrypt, divide the initial plaintext
into a left and right half, 32 bits apiece,
denoted L0 and R0.
Then for each i, i=1,...16:
let Li be set equal to Li-1 ^ Pi;
let Ri be set equal to F(Li) ^ Pi;
then swap Li and Ri.
Finally, swap Li and Ri (i.e., undo the 16th swap).
Then:
Let Rfinal be set equal to R16^P17;
Let Lfinal be set equal to L16^P18;
Finally, rejoin the right and left halves,
denoted Lfinal and Rfinal.
Decryption is the same as encryption,
except that P1,... P18
are used in reverse order.
Subkeys are calculated as follows:
1. Initialize P'1,... P'18,
and then S'1,0,... S'4,255, in order,
using the hexadecimal expansion of pi.
2. Obtain the secret-permutation array,
P1,... P18, by letting
Pi be set equal to P'i ^ Ki.
3.
4.
ASYMMETRIC ENCRYPTION.
In 1976, Diffie, Hellman, and Merkle
introduced the paradigm of public-key
or asymmetric encryption.
In classical, symmetric encryption, the sender and receiver
use essentially the same key, or paired keys which are obvious
(symmetric) transformations of one another.
In asymmetric encryption, the receiver creates a public-key
and a private-key. The public-key may be distributed
without restriction. The private-key is known only to the receiver,
so that there are no problems incumbent upon giving a key to
a possibly untrustworthy sender. The basic mathematical principle
underlying asymmetric encryption is that it is an enormous
computational task to factor a number which is the product
of two large prime numbers.
The most popular asymmetric encryption algorithm
is the RSA public-key encryption algorithm
(named after its authors: Ron Rivest, Adi Shamir, and Leonard Adleman).
Prof. Rivest's security and cryptography webpage is available at URL:
http://theory.lcs.mit.edu/~rivest/crypto-security.html
Every significant public-key encryption algorithm has been patented.
The U.S. patent for the RSA public-key encryption algorithm
expired on September 20, 2000.
However, you should not take this fact as a go-ahead
to freely use the above methodology.
Patent-holders are notoriously jealous of a successful invention,
and it is likely that variants of the original idea have
been repatented in another form that will get you in trouble
if you tread upon it. The pharmaceutical industry is notorious
for this sort of thing.
You should first consult a patent attorney.
Better yet, purchase a software license from a reputable vendor,
and let the experts argue about who owns what.
In asymmetric encryption, the public-key is the product of two,
very large prime numbers, whereas the private-key is the factors themselves.
The underlying principle of asymmetric encryption
is the mathematical conjecture (i.e., unproved mathematical assertion)
that it is an enormous computational task
to factor a number which is the product of two large prime numbers.
This conjecture has never been proved mathematically,
but likewise in the past two decades of serious investigation
by the world's best cryptanalysts, nobody has successfully
challenged this mathematical assertion.
SAMPLE CALCULATION FOR RSA ENCRYPTION.
The RSA method is breathtakingly elegant in its simplicity.
Beyond the need for obtaining large prime numbers and performing
large-integer arithmetic, the concept is so simple that it
can be explained to a bright college undergraduate in mathematics.
The big problem with public use of RSA is that it is patented.
The essential steps in asymmetric encryption by the RSA Method are:
PUBLIC KEY:
n = product of two prime numbers, p and q.
e is relatively prime to (p-1)*(q-1).
PRIVATE KEY:
d = (e-1) mod((p-1)(q-1)).
ENCRYPTION:
c = (te) mod n.
DECRYPTION:
t = (cd) mod n.
where n is the (public) product,
e is the public (=encryption) key,
d is the private (=decryption) key,
t is the plaintext, and c is the ciphertext.
The term x modulo n, or x mod n,
denotes the (whole number) remainder
of the division of x by n.
Modulo arithmetic, or so-called 'clock arithmetic',
is the mathematical method by which we determine,
say, that five hours after ten o'clock, it is three o'clock.
That is, the ordinary clock is a modulo-12 device,
and [(5+10) mod 12] equals 3.
Similarly, the second-hand and minute-hand on the clock
are modulo-60 devides, and the military clock
is a modulo-24 device.
Modulo arithmetic has the fantastic advantage
that integer arithemetic can be performed
on huge integers with absolute accuracy,
without having intermediate calculations
exceed a predetermined size, namely,
the square of the modulus.
Modulo arithmetic is one of the pillars of modern cryptography.
After determining prime numbers p and q,
then calculating n, e, and d, one discards p,q.
The receiver distributes numbers (n,e) publicly, whereas
d is kept secret and known only to the receiver.
The receiver needs numbers (n,d) to decrypt his messages.
The paradigm of asymmetric encryption may be illustrated
by a simple example that can be verified on a hand calculator.
(Actually, the hand calculator is a bit tedious;
it is probably faster to write a program in QBasic,
Visual Basic, or PERL, if you know these languages.)
In the example, let p=31 and q=37.
These are not large prime numbers, but they serve as a didactic example.
Then n= 31*37 = 1147.
The next task is to select e, which must be relatively prime
(i.e., not share a common factor larger than one)
with ((p-1)*(q-1)) = 30*36 = 1080.
For this simple example, one may simply try out
all the possible values of e less than
sqrt(1081)
(the so-called SIEVE OF ERATOSTHENES).
That is, one requires a value of
e
such that
there is a whole-number d such that
d * e = 1081.
For really big primes, there are more efficient ways
to obtain d,e. In the present example, e=23, d=47, and
d * e = 23 * 47 = 1081 = (1) mod 1080 = (1) mod ((p-1)*(q-1)).
That is, '1 mod 1080' denotes that the remainder
of 1081 divided by 1080 is 1. Since d * e = 1
can be written equivalently as
d = (e-1),
we can assert that:
d = (23-1) mod(30*36) = 47.
Let the plaintext message be the number t=13.
Then we may encrypt the plaintext message, t,
according to the formula in Table 1 as:
c = (t3) mod n = (1323) mod 1147 = 520.
That is:
t1 = 13, and (t1) mod 1147 = 13.
t2 = 169, and (t2) mod 1147 = 169.
t3 = 2197, so that (t3) mod 1147 = 1050.
The calculation may be continued on a small calculator
by noting that:
[t4 mod 1147] equals [t * [(t3) mod 1147] mod 1147]
[t5 mod 1147] equals [t * [(t4) mod 1147] mod 1147]
....
c = [1323 mod 1147]
equals [t * [(t22) mod 1147] mod 1147]
c = (1323) mod 1147 = 520.
In this manner, the whole-numbers in the intermediate calculations
never exceed 11472 in size.
When the receiver obtains the ciphertext, c=520,
it may be decrypted by the formula (Table 1):
t = (cd) mod n = (52047) mod 1147 = 13.
Note that not even the sender can decrypt the initial message, t,
after it has been encrypted into ciphertext, c.
LEGAL STATUS OF ASYMMETRIC CRYPTOGRAPHY.
At this time, every significant public-key encryption algorithm
is patented, and several legal challenges to these patents
to date have all been decided in favor of the patent holders.
The U.S. patent for the RSA public-key encryption algorithm
expired on September 20, 2000.
However, you should not take this fact as a go-ahead
to freely use the above methodology.
Patent-holders are notoriously jealous of a successful invention,
and it is likely that variants of the original idea have
been repatented in another form that will get you in trouble
if you tread upon it. The pharmaceutical industry is notorious
for this sort of thing.
You should first consult a patent attorney.
Better yet, purchase a software license from a reputable vendor,
and let the experts argue about who owns what.
2, 3, 5, 7, 11, 13, 17, 19, 23, 29, 31, 37, 41, 43, 47, 53, 57, 59, 61, 67, 71, 73, 79....