💾 Archived View for gemini.spam.works › mirrors › textfiles › law › primes.txt captured on 2022-04-28 at 22:23:55.
⬅️ Previous capture (2020-10-31)
-=-=-=-=-=-=-
Primes, Codes and the National Security Agency
Susan Landau
Physicists lost their innocence and freedom from government controls with Los
Alamos. For biologists that time came in 1976 with National Institutes of
Health regulation of recombinant DNA experiments. Mathematicians have been
free from restraint -- until now. The National Security Agence (NSA) has
asked for and recieved an agreement of prior review on articles concerning
cryptography. It recently sought to fund proposals for research in
computational mathematics submitted to the National Science Foundation (NSF).
Mathematics rarely makes the headlines, but the article on the front page of
The New York TImes of August 27, 1980 was startling -- "Science Agency Blocks
Funds to Aid Research on Computer Coding." Even more surprising is that the
NSA is funding research on factoring integers. Factoring is so basic a
problem that schoolchildren are asked to do it; how could it be a threat to
national security?
The interest stems from the crucial role that primes and factoring play in a
new mathcmatical cryptographic scheme. For centuries cryptography was the
domain of the military, but an increasing reliance on computer data banks for
anything from medical histories to credit records has changed that. There is
a growing need for secure transmission of data which has made cryptography an
active area of research in the private sector. The critical component of the
sending of secret messages is a secure cipher. If many messages using the
same code are intercepted, the cipher may be discerned by knowing the
frequency distribution of letters in the language. Frequent changes of the
cipher removes this problem, only to raise another: how to transmit the
encryption scheme securely?
Seeking a way out of this dilemma, Whitfield Diffie and Martin Hellman of
Stanford and Ralph Merkle of Berkeley proposed Public-Key cryptography in
1976. In short, Diffie, Hellman and Merkle envisaged an encryption mechanism
in which even if the encryption method were known, decryption would be
difficult and take years. By the time intercepted messages could be
unraveled, the information would be outdated and useless. Encryption would be
a "trapdoor"; its strength would lie in the inherent infeasibilty of certain
computations. At the time of Diffie and Hellman suggested several
possibilities for such schemes but saw no workable method. Three computer
scientists then at MIT, Ronald Rivest, Adi Shamir and Leonard Adleman did.
They had a clever idea to exploit the contrast between the speed of primality
testing and the apparent difficulty of factoring. Multiplying together two
large primes would be a trapdoor from which factoring would be the exit.
The groundwork for their scheme had been laid in the early seventies. While
logicians have wrestled for decades with the question of decidability, the
issue in computer science instead has been complexity: on a problem of imput
size "m", how many steps does it take as a function of m to solve the problem?
Answers to this question involve obtaining algorithms which provide an upper
bound on the complexity of the problem, and lower bounds which show that any
comceivable algorithm will require a certain number of steps. Exhibiting
lower bounds is hard; for example the present best lower bounds on the
complexity of multiplying two m x m matrices is O(m2) (an obvious bound since
there are m2 entries), while the best algorithm is O(m2.496).
The critical distinction comes between problems with polynomial time
algorithms, and those which require exponential running time. The complexity
of factoring integers is unknown, but best present factoring algorithms work
in m1.6(m/log m)^.5 steps on an integer of m digits, which means that
factoring a random one hundred digit number is essentially infeasible.
Primality testing would appear to be as difficult, but in 1974 Gary Miller of
Berkely devised an algorithm which uses the Extended Riemann Hypothesis (ERH)
to test primality of an m digit integer in O(m4) steps. ERH guarantees the
existence of a quadratic non-residue less than O(log2p) in ?/p?, which
Miller's algorithm needs to check primality. An approach which avoids the use
of ERH was found by Robert Solovay of IBM and Volker Strassen of the
University of Zurich; theirs is a probabilistic algorithm which test primality
of an m digit integer in O(m) steps. If the integer to be checked is prime,
the Solovay-Strassen test responds "prime"; if the integer is composite, with
probability no greater than one-half, the test declares it to be prime.
Suppose a is an integer less than n; and let (a/n) be the Jacobi symbol of a
on n. If n is prime, then (a/n)=a(n-1)/2 mod n. Solovay and Strassen noted
that the set {a|(a/n)=a(n-1)/2 mod n} is a proper subgroup of (?/n?)* for
composite n. This means that at least half the a's less than n and relatively
prime to n do not satisfy (a/n)=a(n-1)/2 mod n. The Solovay-Strassen test
computes (a/n) (by quadratic reciprocity) and a(n-1)/2 mod n; it the two are
not equal, the test responds "composite," otherwise it calls the integer
"prime". The algorithm runs k independent trials, if any respond composite,
the integer is composite, and is discarded. If all the trials say the integer
is prime, then the probability that it is composite is less than 2-k. Since
Miller's algorithm depends on ERH, and the Solovay-Strassen procedure is
probabilistic, the existence of a polynomial time algorithm remains an open
question. In 1980 however, Adleman, Robert Rumely, then at MIT, and Carl
Pomerance of the University of Georgia developed a subexponential algorithm;
their test runs in O(mc log log n) steps on an m digit integer, where c is a
constant. The upshot of these results is that within fifteen seconds a
computer can check primality of a fifty-digit number.
The MIT group used the contrasts in complexity to create a simple and elegant
Public-Key system. Each participant in the cryptosystem finds two large
primes (about 1050) p and q by one of the fast primality algorithms. Let n =
pq, and let ?(n) be the Euler phi-function of n. Each participant also
chooses an "a", an integer which is less than n and which is relatively prime
to ?(n): such an integer can easily be found since most integers less than n
are relatively prime to ?(n)=(p-1)(q-1). Thus choose a less than n and test
whether (a,?(n))=1; if not, repeat until an a which satisfies the conditions
is found. The Public-Key book prints each participant's n and a. suppose the
Bank of England wants to communicate with the Federal Reserve. The Bank of
England would proceed as follows:
1) Translate the message into numbers, say A = 01, B = 02, etc.
2) Break the message into blocks of convenient size.
3) Consult the Public-Key book for the recipient's n and a.
4) Send each block as (block)a mod n.
Decryption is simple for the reciepient. Since (a,?(n))=1, there exist x and
y such that ax+?(n)y=1, and x and y can be quickly computed from a and ?(n).
The Fed would decode as follows:
1) Break the message up into blocks.
2) For each block, compute (block)x mod n.
3) Glue the blocks back together.
4) Decode by 01=A, 02 = B, etc.
This yields the original message, since
(blocka)x=(block)ax=(block)1-?(n)y=(block) mod n,
by Fermat's Little Theorem. The Fed decodes the communication easily, since
it takes polynomial time to compute x given ?(n). An interceptor of the
communication could do exactly the same calculation, except that he knows n,
not ?(n). The standard way to compute ?(n) is to factor n, and in fact,
Miller has shown that calculating ?(n) is polynomial time equivalent to
factoring n. Since n is the product of two fifty-digit primes, it is
infeasible to factor it using best known algorithms.
Rivest, Shamir and Adleman announced their result in April 1977. The public
became aware of it when Martin Gardner described the system in his
Mathematical Games column of the August 1977 Scientific American . The
discovery also attracted attention from other circles. Shortly before Rivest
was scheduled to present the work at an Institute of Electrical and
Electronics Engineers (IEEE) conference in Ithaca, New York, the IEEE recieved
a letter from one J. A. Meyer of Bethesda, Maryland, warning that publication
of cryptography results might be in conflict with the 1954 Munitions Control
Act which regulated the flow of weapons and sensitive equipment to foreign
countries. Meyer also said that dissemination of the conference proceeding
abroad might be illegal. On the advice of the MIT lawyers, Rivest suspended
sending out preprints.
A reporter from Science , Deborah Shapley, soon discovered that Meyer was
listed as an employee of the NSA. The NSA denied involvement with the letter,
and a spokesman claimed that J. A. Meyer had written it as a private citizen.
Rivest, Shamir, and Adleman decided to present their results at the conference
and to resume mailing of their paper.
Nothing was heard from the NSA for a year and a half, until a speech by its
Director, Admiral Bobby Inman, in 1979. He said that open publication of
research in crryptography was harmful to the national security because it
interfered with the NSA's ability to gather and protect intelligence, and
urged that a dialogue between the NSA and the academic community begin. The
American Council on Education proposed the formation of the Public
Cryptography Study Group (PCSG), with eight members from the academic
community (the majority of them mathematicians and computer scientists), and
one member from the NSA, Daniel Schwartz, a lawyer.
In a series of meetings during 1980-1981, the NSA argued for voluntary
agreement regarding publication of cryptography reseach. The agency claimed
that academic work might inadvertantly compromise United States encryption
schemes. Research on the weaknesses of cryptosystems might also lead foreign
governments to adopt more sophisticated systems, thus denying the U.S. nededed
intelligence. Although it preferred a voluntary agreement, the NSA made clear
that it was also considering seeking statutory authority for prepublication
review of sensitive material. (As precedent, the NSA cited two Federal laws:
the Arms Export Control Act [22 U.S.C. 2778], which restricts foreign
dissemination of certain information relating to cryptology and supercedes the
1954 Munitions Control Act, and Section 181 of Title 35 U. S. C. which
permits the imposition of a secrecy order upon a patent application when
issuance of a patent would be harmful to national security. Since algorithms
and scientific papers are not patentable, neither related to domestic release
of nongovernmental research in cryptography.) On January 5, 1981, the PCSG
approved a two-year experiment under which the NSA would inform the academic
community of its interest in reviewing cryptography papers prior to
publication. Compliance would be voluntary, and review prompt. If the NSA
wanted to delete portions of a paper, or prevent publication, it would first
consult with an advisory panel (whose members would have top security
clearance),. although the NSA would not be bound by the decisions of the
advisory group. Changes would be explained to the greatest degree possible.
One committe member, George Davida, professor of computer science
at the University of Wisconsin, issued a dissenting report. He argued that
the NSA's attempt to control publication of cryptography research was of
questionable legality, and he called attention to a memorandum the Justice
Department had issued stating that, "It is our view that the existing
provisions of the ITAR [Internationl Traffic in Arms Regulation of the
Arms Export Control Act] are unconstitutional insofar as they establish
prior restraint in disclosure of cryptographic ideas and information
developed by scientists and mathematicians in the private sector." Davida
contended that the risks to the NSA were far outweighed by the benefits to
the public, and that the direction and quality of research in cryptography
would be seriously affected by the withholding of results. Rather than
limit public research, the NSA should "perform its mission in the
old-fashioned way: stay ahead of others," Davida bluntly suggested.
The situation grew more serious in August 1980 with the renewal of Leonard
Adleman's NSF grant. His budget had already been renegotiated when Adleman
was informed that the NSF would be unable to fund part of it due to 'national
security reasons." NSF would support Adleman's work on the complexity of
number-theoretic problems and on VLSI (chip design), but declined to support
his research in cryptography or related problems. Shortly afterwards Adleman
recieved a call from Admiral Inman, who offered that the NSA fund Adleman's
work. Because NSF funds are limited, the procedure has always been that if a
mission agency was interested in funding a proposal, it would do so instead of
NSF. The issue here though was disclosure; if the NSA supported Adleman's
research, might it classify it?
THIS PARAGRAPH COULD NOT BE READ IN FROM DISK. Shit
Subsequent to this, a subcommittee of the NSF Mathematics and COmputer
Sciences Advisory Subcommittee was convened to discuss NSF's role in
supporting cryptology research. On July 13, 1981, it issued its report, which
stressed the importance of cryptology to business and private citizens.
"Tampering with information related to such things as electronic funds
transfers? is a new threat which can be posed by criminal, terrorist or enemy
agents to personal, corporate or national security ? it is imperative that
steps be taken to limit access to this information," the report said. The
panel expressed concern that NSF's budget limitations might soon lead the NSA
to dominate the field of cryptography, and recommended that the NSF encourage
the Department of Commerce to fund research in this area. The Public
Cryptography Study Group guidelines came in for sharp criticism. "The
proposed system of prepublication review is unnecessary, unprecedented, and
likely to cause damage to the ability and willingness of Americaan research
scientists to stay at the forefront of research in public sector uses of
cryptology." Finally, the NSF report observed that cryptography is no more of
a threat to national security than many areas of basic research, but that it
was distinguised by the fact that a single government agency had controlled
the area for nearly thirty years.
Davida and others agrue that national security is imperiled more by the lack
of secure encryption systems in the commercial environment than it is by the
knowledge garnered by foreign powers from the publication of cryptography
research. There can be little doubt of the importance of cryptography to
industry, business, banking, and the Department of Commerce, even the
Department of Agriculture. In 1972-1973 the Soviets were able to purchase
record amounts of grain because of information they had obtained by
eavesdropping on calls to and from the Department of Agriculture.
Long-distance calls are transmitted by microwave, and are not encoded; it is a
simple matter to intercept and listen to messages. Information about grain
transactions are not the only communications to travel insecurely; everything
from banking information to trade secrets is subject to the same type of
attack. Dissemination of research on cryptography may make the NSA's job more
difficult. In a society where information is a commodity, there is no easy
path between Scylla and Charybdis.
In the two years since the PCSG recommendations and the decision that both NSF
and NSA would fund cryptology research, the mathematics community has reached
a temprory accommoodation with the situation. The AMS has chosen to
publicize, without endorsement, any request by the NSA for individuals to
participate in the review process. The leading professional organization in
computer science, the Association for Computing Machinery, encourages authors
of papers in cryptology to submit their articles to the NSA for prepublication
review, but does not enquire if that has been done. The NSA has recieved
copies of thirty-five papers, and has suggested "minor changes" in two of
them. New funding procedures have not had a sufficient time for evaluation.
The NSA has funded four grants, while the NSF has experienced a ten percent
increase in cryptology proposals submitted, the same growth it has had in
othere areas of theoretical computer science. But two years is a short time
to measure change in a research community, and it is probably too soon to tell
if the NSA restraints will have a chilling effect on research in public sector
cryptography.
NSA actions relate directly to basic research in mathematics and computer
science. For example, the security of the Rives, Shamir and Adleman system
relies on factoring being hard. Does the NSA propose to suppress
investigations on factoring integers? THe Atomic Energy Act created a
precedent for private work being "born classified," but there is a sharp
distinction between ideas which apply to the building of bombs, and those
which relate to the security of computer systems. If work on cryptography is
restricted in the United States, there is nothing to prevent researchers in
other countries from pursuing such inquiries. At the time of hearing on the
Atomic Energy Act, Enrico Fermi commented, "Unless research is free and
outside of control, the United States will lose its superiority in scientific
pursuit." Scientific questions do not arise in a vacuum, nor do ideas develop
under the threat of restraint. Restricting the freedom on inquiry in which
science thrives is not a decision to be taken lightly.
Bibliography
Adleman, L., Pomerance, D., and Rumely, R., On distinguishing prime numbers
from composite numbers, Annals of Mathematics, (to appear).
Broad, W., Evading the Soviet Ear at Glen Cove, Science, 3 September 1982,
pages 910-911.
Coppersmith, D., and Winograd, S., On the asympotic complexity of matrix
multiplication, Proceedings of the 22nd Annual Symposium on Foundations of
Computer Science, October 1981, pages 80-92.
Davida, G., Safety in numbers, The Sciences, July/August 1981, pages 9-14.
Diffie, W., and Hellman, M., New directions in cryptography, IEEE
Transactions on Information Theory, November 1976, pages 644-654.
Inman, B. R., Cryptography research funding, Science, 10 October 1980, page
134.
Kolata, G. B., Cryptography: A new clash between academic freedom and national
security, Science, 29 August 1980, pages 995-996.
Kolata, G. B., NSA seeks research proposals, Science, 11 September 1981, page
1233.
Kolata, G. B., NSA asks to review papers before publication, Science, 19
March 1982, page 1485.
Lehmer, D. H., Strong Carmichael numbers, Journal of the Austrailian
Mathematical Society, Series A, Vol. 21, June 1976, pages 508-510.
Mathematical and Computer Sciences Advisory Subcommittee, The role of the NSF
in supporting cryptological research, A Report to the National Science
Foundation By its Mathematics and Computer Sciences Advisory Subcommittee,
July 19, 1981.
Miller, G. L., Riemann's hypothesis and test for primality, Proceedings of
the Seventh Annual ACM Symposium on Theory of COmputing, May 1975, pages
234-239.
Public Cryptography Study Group, Report of the Public Cryptography Study
Group, American Council on Education, February 1981; reprinted in the Notices
of the American Mathematical Society, October 1981, pages 518-526.
Rivest, R. L., Shamir, A., and Adleman, L., A method for obtaining digital
signatures and Public-Key cryptosystems, Communications of the ACM, February
1978, pages 120-126.
Shapley, D., and Kolata, G. B., Cryptology: Scientists puzzle over threat to
open research, publication, Science, 30 September 1977, pages 1245-1349.
Solovay, R., and Strassen, V., A fast Monte-Carlo test for primality, SIAM
Journal of Computing, 1977, pages 84-85.
U.S. Congress, House of Representatives, Thirty-fourth Report by the Committee
on Government Operations, The Governmaent classsification of private ideas
together with additional views, House Report 96-1540, December 1980.
Walsh, J., Shunning cryptocensorship, Science, 12 June 1981, page 1250.
Wilford, J. N., Science agency blocks funds to aid research on computing
coding, The New York Times, August 27, 1980, page A1.
X-=-=-=-=-=-=-=-=-=-=-=-=-=-=-=-=-=-=-=-=-=-=-=-=-=-=-=-=-=-=-=-=-=-=-=-=-=-X
Another file downloaded from: NIRVANAnet(tm)
& the Temple of the Screaming Electron Jeff Hunter 510-935-5845
Salted Slug Systems Strange 408-454-9368
Burn This Flag Zardoz 408-363-9766
realitycheck Poindexter Fortran 415-567-7043
Lies Unlimited Mick Freen 415-583-4102
Tomorrow's 0rder of Magnitude Finger_Man 408-961-9315
My Dog Bit Jesus Suzanne D'Fault 510-658-8078
Specializing in conversations, obscure information, high explosives,
arcane knowledge, political extremism, diversive sexuality,
insane speculation, and wild rumours. ALL-TEXT BBS SYSTEMS.
Full access for first-time callers. We don't want to know who you are,
where you live, or what your phone number is. We are not Big Brother.
"Raw Data for Raw Nerves"
X-=-=-=-=-=-=-=-=-=-=-=-=-=-=-=-=-=-=-=-=-=-=-=-=-=-=-=-=-=-=-=-=-=-=-=-=-=-X