Path: utzoo!mnetor!uunet!husc6!hao!gatech!bbn!uwmcsd1!csd4.milw.wisc.edu!markh
From: markh@csd4.milw.wisc.edu (Mark William Hopkins)
Newsgroups: sci.crypt
Subject: Re: "Secure" encryption
Message-ID: <4224@uwmcsd1.UUCP>
Date: 16 Jan 88 02:58:16 GMT
References: <8801132010.AA15994@decwrl.dec.com>
Sender: daemon@uwmcsd1.UUCP
Reply-To: markh@csd4.milw.wisc.edu (Mark William Hopkins)
Organization: University of Wisconsin-Milwaukee
Lines: 41
Summary: An encryption based on an unsolveable problem (?)

In article <8801132010.AA15994@decwrl.dec.com> kruger@whyvax.dec.com (Hart for CCCP chief in '88) writes:
>Maybe someone can answer a question that's been bothering me for a while now. Ifyou need an absolutely (provably) secure code, the key must be as long as the
>message. Even if it is not, a very short (and fairly random) datum will be hard to decode. So why not embed the real key in the message? ie, the external "key"
>is designed only to decrypt the randomly selected internal key, which is the
>one that decodes the real message. One of the modes of DES does this, but each
>successive key is no longer than the previous one. I am proposing a key of
>perhaps 128 bytes. It is extremely random (this is a technical point on which
>I have no expertise -- I will assume a REALLY random technique, ie not a pseudo-random sequence whose mechanics we know, but some physical process we don't,
>like radiation counts or something. Now, your 16 byte key need only decrypt a
>patternless "plaintext" key. And the longer key can be used to make a much
>nastier encryption. Why isn't this done?
>
>dov
>
>"Disclaimers are bullshit"

This problem may briing a quick resolution to one of the issues brought up.

This is a message in a code based on the Post Correspondence Problem.  Its
characteristic is that neither the message nor the key is necessary!

There is an obvious problem in receiving an encrypted message based on the
Post Correspondence Problem.  How does one parse it?  The answer, incredibly
enough, is to send the message in unencrypted form!  But, you might wonder,
doesn't that defeat the purpose of using encryption?  No, as you will see.

Problem:  Find the actual message encrypted below.

Hint: THIS IS NOT THE ACTUAL MESSAGE (which, of course, is why it does not
need to be transmitted.)

MESSAGE:

51405020503150820087603150820087641209075140587651405020512
208762515216508051405049925152130587685051122008200251525431220  

A solution will be given at this time in the year 2001.  If this problem 
proves to be too difficult (or impossible) then I will also give out the key.
Having the key, though, will not help in the least bit, as it is totally
useless. Using computers will not help either, since this code is based on the 
unsolveable Post Correspondence Problem (or is it?).