1995-08-05 - Re: RSA has been proved correct

Header Data

From: solman@MIT.EDU
To: tcmay@sensemedia.net (Timothy C. May)
Message Hash: 1e656aab6a92e5e86c72801ca157d26e0516739fabbe60fde81e0fa64a9e02b4
Message ID: <9508050806.AA22214@ua.MIT.EDU>
Reply To: <ac470d240502100447cc@[]>
UTC Datetime: 1995-08-05 08:06:54 UTC
Raw Date: Sat, 5 Aug 95 01:06:54 PDT

Raw message

From: solman@MIT.EDU
Date: Sat, 5 Aug 95 01:06:54 PDT
To: tcmay@sensemedia.net (Timothy C. May)
Subject: Re: RSA has been proved correct
In-Reply-To: <ac470d240502100447cc@[]>
Message-ID: <9508050806.AA22214@ua.MIT.EDU>
MIME-Version: 1.0
Content-Type: text/plain

Tim quoth:

|> I was reading the logic programming/theorem proving chapter of my new
|> Russell and Norvig book on AI, and came across something I once knew about
|> but had forgotten: the Boyer-Moore theorem prover was applied to the RSA
|> algorithm and the correctness of it was verified. Correctness in the sense
|> of showing that outputs match formal specs, for all inputs.

|> The paper is: Boyer, R.S and Moore, J.S. (1984). Proof checking the RSA
|> public key encryption algorithm, "American Mathematical Monthly,"
|> 91(3):181-189.

Given the enormous difficulty of ensuring security in a world of
ubiquitous distributed computing, I'm as big a fan as any of formal
methods. But Tim's post hammers home the big fault of formal methods:
the possibility that people will come to rely upon them. I have
paranoid visions of people finally accepting formal methods in a decade
or so, and then becoming dependent on them... forgeting the enormous
potential for error that will always exist in such systems.

If somebody told me that intentionally letting a few violent criminals
free each year is a good idea because it would keep me on my toes, I
would think that person is an idiot. But I'm not entirely convinced that
it is a bad idea to avoid formal methods because they could breed