Cryptography-Digest Digest #721, Volume #13 Tue, 20 Feb 01 11:13:00 EST
Contents:
Reverse encoding question^2 (Paul Starzetz)
Re: MQV implementation ("Alexander Schmitt")
Re: Is there an algorithm to sequentially enumerate all transcendental numbers?
(David C. Ullrich)
Re: Given any arbitrary numbers a and b. Can I ALWAYS find a transcendental number
between a and b? (David C. Ullrich)
Re: The Kingdom of God (Alun Jones)
Re: The Kingdom of God (William Hugh Murray)
Re: Given any arbitrary numbers a and b. Can I ALWAYS find a transcendental number
between a and b? (Dave Seaman)
Re: CipherText patent still pending (John Myre)
----------------------------------------------------------------------------
From: Paul Starzetz <[EMAIL PROTECTED]>
Subject: Reverse encoding question^2
Date: Tue, 20 Feb 2001 14:15:46 +0100
Hi ppl,
thanks for the answer to my previous posting, I didn't realize that my
problem is really simple :-)
Here comes a real one:
given a cipher C (working on 8 byte long blocks) and encrypted text X,
what plaintext shall I use to
obtain X, _if_ the encryption key of the cipher C is known AND we need
to change the last plain text block to contain some function F of the
preceeding plain text blocks and one free 32 bit value.
I have to solve this problem for either blowfish or 3des and the
function F to be the well known (I think) crc32 code.
Small example:
I have to produce 3des-cbc encrypted data having full controll over the
used encryption key and the one 32bit free value, but after encryption
the output has to be e.g.:
0xabdc0001 whatever 0xabdc0001 whatever ... 0xabdc0001 whatever [DEFINED VALUE]
[NOT IMPORTANT]
<-- CBC block 0 --> <-- CBC block 1 --> ... <-- CBC block N-1 --> <------- CBC
block N ------>
8 bytes 8 bytes 8 bytes 8
bytes
where whatever doesn't matter (I can set it to be whatever I want),
0xabdc0001 is the value I want to be the first 32 bits of every 8 byte
block (I must be able to deal with any integer here) and DEFINED VALUE
is what I want to be in the last encrypted data block. NOT IMPORTANT
stands for the resulting encrypted data after we stored the crc32 in the
plain text but the value doesn't matter (it only needs to be decryptable
again and result in valid crc32 value at this position after decryption
of the whole packet)
before encryption we would have the following data:
[plain block 0] [plain block 1] ... [plain block N-1] [FREE VALUE CRC32]
where plain blocks results from decrypting cipher blocks 0...N-1 (with
the 0xabdc0001's), crc32 is the crc32 checksum taken over the plain text
blocks 0...N-1 AND the FREE VALUE (8*N+4 bytes). FREE VALUE is the 32
bit value we can vary. We can change the FREE VALUE before crc32 is
calculated but after encryption of the last (Nth) block I want to obtain
DEFINED VALUE in the place of FREE VALUE. DEFINED VALUE is some integer,
if it would simplify this problem, it can be assumed to be 0x00000000.
So the problem I have is that the CBC des (or another cipher) code would
encrypt the whole 8 byte block mixing the value of CRC32 with free
value. I wonder if there exists a solution to this.
I attach the crc32 code, if it isn't so common...
Paul.
/* ============================================================= */
/* COPYRIGHT (C) 1986 Gary S. Brown. You may use this program, or */
/* code or tables extracted from it, as desired without restriction. */
/* */
/* First, the polynomial itself and its table of feedback terms. The */
/* polynomial is */
/* X^32+X^26+X^23+X^22+X^16+X^12+X^11+X^10+X^8+X^7+X^5+X^4+X^2+X^1+X^0 */
/* */
/* Note that we take it "backwards" and put the highest-order term in */
/* the lowest-order bit. The X^32 term is "implied"; the LSB is the */
/* X^31 term, etc. The X^0 term (usually shown as "+1") results in */
/* the MSB being 1. */
/* */
/* Note that the usual hardware shift register implementation, which */
/* is what we're using (we're merely optimizing it by doing eight-bit */
/* chunks at a time) shifts bits into the lowest-order term. In our */
/* implementation, that means shifting towards the right. Why do we */
/* do it this way? Because the calculated CRC must be transmitted in */
/* order from highest-order term to lowest-order term. UARTs transmit */
/* characters in order from LSB to MSB. By storing the CRC this way, */
/* we hand it to the UART in the order low-byte to high-byte; the UART */
/* sends each low-bit to hight-bit; and the result is transmission bit */
/* by bit from highest- to lowest-order term without requiring any bit */
/* shuffling on our part. Reception works similarly. */
/* */
/* The feedback terms table consists of 256, 32-bit entries. Notes: */
/* */
/* The table can be generated at runtime if desired; code to do so */
/* is shown later. It might not be obvious, but the feedback */
/* terms simply represent the results of eight shift/xor opera- */
/* tions for all combinations of data and CRC register values. */
/* */
/* The values must be right-shifted by eight bits by the "updcrc" */
/* logic; the shift must be unsigned (bring in zeroes). On some */
/* hardware you could probably optimize the shift in assembler by */
/* using byte-swap instructions. */
/* polynomial $edb88320 */
/* */
/* -------------------------------------------------------------------- */
static unsigned int crc32_tab[] = {
0x00000000L, 0x77073096L, 0xee0e612cL, 0x990951baL, 0x076dc419L,
0x706af48fL, 0xe963a535L, 0x9e6495a3L, 0x0edb8832L, 0x79dcb8a4L,
0xe0d5e91eL, 0x97d2d988L, 0x09b64c2bL, 0x7eb17cbdL, 0xe7b82d07L,
0x90bf1d91L, 0x1db71064L, 0x6ab020f2L, 0xf3b97148L, 0x84be41deL,
0x1adad47dL, 0x6ddde4ebL, 0xf4d4b551L, 0x83d385c7L, 0x136c9856L,
0x646ba8c0L, 0xfd62f97aL, 0x8a65c9ecL, 0x14015c4fL, 0x63066cd9L,
0xfa0f3d63L, 0x8d080df5L, 0x3b6e20c8L, 0x4c69105eL, 0xd56041e4L,
0xa2677172L, 0x3c03e4d1L, 0x4b04d447L, 0xd20d85fdL, 0xa50ab56bL,
0x35b5a8faL, 0x42b2986cL, 0xdbbbc9d6L, 0xacbcf940L, 0x32d86ce3L,
0x45df5c75L, 0xdcd60dcfL, 0xabd13d59L, 0x26d930acL, 0x51de003aL,
0xc8d75180L, 0xbfd06116L, 0x21b4f4b5L, 0x56b3c423L, 0xcfba9599L,
0xb8bda50fL, 0x2802b89eL, 0x5f058808L, 0xc60cd9b2L, 0xb10be924L,
0x2f6f7c87L, 0x58684c11L, 0xc1611dabL, 0xb6662d3dL, 0x76dc4190L,
0x01db7106L, 0x98d220bcL, 0xefd5102aL, 0x71b18589L, 0x06b6b51fL,
0x9fbfe4a5L, 0xe8b8d433L, 0x7807c9a2L, 0x0f00f934L, 0x9609a88eL,
0xe10e9818L, 0x7f6a0dbbL, 0x086d3d2dL, 0x91646c97L, 0xe6635c01L,
0x6b6b51f4L, 0x1c6c6162L, 0x856530d8L, 0xf262004eL, 0x6c0695edL,
0x1b01a57bL, 0x8208f4c1L, 0xf50fc457L, 0x65b0d9c6L, 0x12b7e950L,
0x8bbeb8eaL, 0xfcb9887cL, 0x62dd1ddfL, 0x15da2d49L, 0x8cd37cf3L,
0xfbd44c65L, 0x4db26158L, 0x3ab551ceL, 0xa3bc0074L, 0xd4bb30e2L,
0x4adfa541L, 0x3dd895d7L, 0xa4d1c46dL, 0xd3d6f4fbL, 0x4369e96aL,
0x346ed9fcL, 0xad678846L, 0xda60b8d0L, 0x44042d73L, 0x33031de5L,
0xaa0a4c5fL, 0xdd0d7cc9L, 0x5005713cL, 0x270241aaL, 0xbe0b1010L,
0xc90c2086L, 0x5768b525L, 0x206f85b3L, 0xb966d409L, 0xce61e49fL,
0x5edef90eL, 0x29d9c998L, 0xb0d09822L, 0xc7d7a8b4L, 0x59b33d17L,
0x2eb40d81L, 0xb7bd5c3bL, 0xc0ba6cadL, 0xedb88320L, 0x9abfb3b6L,
0x03b6e20cL, 0x74b1d29aL, 0xead54739L, 0x9dd277afL, 0x04db2615L,
0x73dc1683L, 0xe3630b12L, 0x94643b84L, 0x0d6d6a3eL, 0x7a6a5aa8L,
0xe40ecf0bL, 0x9309ff9dL, 0x0a00ae27L, 0x7d079eb1L, 0xf00f9344L,
0x8708a3d2L, 0x1e01f268L, 0x6906c2feL, 0xf762575dL, 0x806567cbL,
0x196c3671L, 0x6e6b06e7L, 0xfed41b76L, 0x89d32be0L, 0x10da7a5aL,
0x67dd4accL, 0xf9b9df6fL, 0x8ebeeff9L, 0x17b7be43L, 0x60b08ed5L,
0xd6d6a3e8L, 0xa1d1937eL, 0x38d8c2c4L, 0x4fdff252L, 0xd1bb67f1L,
0xa6bc5767L, 0x3fb506ddL, 0x48b2364bL, 0xd80d2bdaL, 0xaf0a1b4cL,
0x36034af6L, 0x41047a60L, 0xdf60efc3L, 0xa867df55L, 0x316e8eefL,
0x4669be79L, 0xcb61b38cL, 0xbc66831aL, 0x256fd2a0L, 0x5268e236L,
0xcc0c7795L, 0xbb0b4703L, 0x220216b9L, 0x5505262fL, 0xc5ba3bbeL,
0xb2bd0b28L, 0x2bb45a92L, 0x5cb36a04L, 0xc2d7ffa7L, 0xb5d0cf31L,
0x2cd99e8bL, 0x5bdeae1dL, 0x9b64c2b0L, 0xec63f226L, 0x756aa39cL,
0x026d930aL, 0x9c0906a9L, 0xeb0e363fL, 0x72076785L, 0x05005713L,
0x95bf4a82L, 0xe2b87a14L, 0x7bb12baeL, 0x0cb61b38L, 0x92d28e9bL,
0xe5d5be0dL, 0x7cdcefb7L, 0x0bdbdf21L, 0x86d3d2d4L, 0xf1d4e242L,
0x68ddb3f8L, 0x1fda836eL, 0x81be16cdL, 0xf6b9265bL, 0x6fb077e1L,
0x18b74777L, 0x88085ae6L, 0xff0f6a70L, 0x66063bcaL, 0x11010b5cL,
0x8f659effL, 0xf862ae69L, 0x616bffd3L, 0x166ccf45L, 0xa00ae278L,
0xd70dd2eeL, 0x4e048354L, 0x3903b3c2L, 0xa7672661L, 0xd06016f7L,
0x4969474dL, 0x3e6e77dbL, 0xaed16a4aL, 0xd9d65adcL, 0x40df0b66L,
0x37d83bf0L, 0xa9bcae53L, 0xdebb9ec5L, 0x47b2cf7fL, 0x30b5ffe9L,
0xbdbdf21cL, 0xcabac28aL, 0x53b39330L, 0x24b4a3a6L, 0xbad03605L,
0xcdd70693L, 0x54de5729L, 0x23d967bfL, 0xb3667a2eL, 0xc4614ab8L,
0x5d681b02L, 0x2a6f2b94L, 0xb40bbe37L, 0xc30c8ea1L, 0x5a05df1bL,
0x2d02ef8dL
};
/* Return a 32-bit CRC of the contents of the buffer. */
unsigned int
crc32(const unsigned char *s, unsigned int len)
{
unsigned int i;
unsigned int crc32val;
crc32val = 0;
for (i = 0; i < len; i ++) {
crc32val = crc32_tab[(crc32val ^ s[i]) & 0xff] ^ (crc32val >> 8);
}
return crc32val;
}
------------------------------
From: "Alexander Schmitt" <[EMAIL PROTECTED]>
Subject: Re: MQV implementation
Date: Tue, 20 Feb 2001 14:26:29 +0100
> Use the NIST 233 curve. Change out the integer math from the book a
"real"
> integer math package. Use the inversion routine from chapter 11 instead
of
> from 4. Those changes should give you an order of magnitude improvement
with
> no problem.
Now, I have tried to use the chapter 11 inverse routine instead of the
chapter 4 routine.
But it will be hangs on the program in an endless loop in the onb_inv
routine. Any hints what could be gone wrong at my adaptation? I have used
the routine nearly 1:1 from the book.
With the normal ONB inversion routine it works.
Are there any math libs which can be suggested for a fast implementation of
the big integer maths?
Any hints are welcome!
Alex
------------------------------
From: [EMAIL PROTECTED] (David C. Ullrich)
Crossposted-To: sci.math
Subject: Re: Is there an algorithm to sequentially enumerate all transcendental
numbers?
Date: Tue, 20 Feb 2001 14:13:38 GMT
Reply-To: [EMAIL PROTECTED]
On Mon, 19 Feb 2001 11:37:47 -0500, jtnews <[EMAIL PROTECTED]>
wrote:
>jtnews wrote:
>>
>> Is there an algorithm to sequentially enumerate
>> all possible transcendental numbers?
>>
>> I want to be able to generate very long
>> passphrases but at the same time be able
>> to express them succinctly in the form of mathematical
>> expressions.
>
>
>Let me clarify what I mean by sequentially enumerate.
I don't know why you think people misunderstood this.
The answer is simply _no_. Looked to me like most
replies understood the question - you should look again
at the answers.
[explanation of the meaning of 'sequentially enumerate'
that seems perfectly consistent with what most replies
took it to mean snipped]
------------------------------
From: [EMAIL PROTECTED] (David C. Ullrich)
Crossposted-To: sci.math
Subject: Re: Given any arbitrary numbers a and b. Can I ALWAYS find a transcendental
number between a and b?
Date: Tue, 20 Feb 2001 14:26:18 GMT
Reply-To: [EMAIL PROTECTED]
On Tue, 20 Feb 2001 12:56:33 GMT, [EMAIL PROTECTED]
(John Savard) wrote:
>On 19 Feb 2001 23:56:09 -0500, [EMAIL PROTECTED] (Dave Seaman)
>wrote, in part:
>
>>>The algebraic numbers are nowhere dense.
>
>>No, the algebraic numbers are everywhere dense. So are the
>>transcendentals.
>
>>The Cantor set is nowhere dense.
>
>Being dense myself, I used the wrong definition of 'dense'. What is
>the name of the property of having measure n over a line segment of
>length n?
"Has full measure" is equivalent to this for finite n - in general
"has full measure" means the complement has measure zero.
But I don't think that's the phrase you really wanted to use
here in place of "dense". The purely topological concept that
you mis-labelled as "dense" is "has empty interior".
Try it. The set of algebraic numbers has empty interior.
Yup, that's what you meant.
>John Savard
>http://home.ecn.ab.ca/~jsavard/crypto.htm
------------------------------
Crossposted-To: alt.security,comp.security,alt.2600
From: [EMAIL PROTECTED] (Alun Jones)
Subject: Re: The Kingdom of God
Date: Tue, 20 Feb 2001 14:20:41 GMT
In article <cnqk6.145873$[EMAIL PROTECTED]>, "Jashter"
<[EMAIL PROTECTED]> wrote:
> Yeah, but then you must wonder if there really is a god in the first
> place...
. . . Not to mention whether or not He could build a system that even He
could not penetrate :-)
Alun.
~~~~
[Note that answers to questions in newsgroups are not generally
invitations to contact me personally for help in the future.]
--
Texas Imperial Software | Try WFTPD, the Windows FTP Server. Find us at
1602 Harvest Moon Place | http://www.wftpd.com or email [EMAIL PROTECTED]
Cedar Park TX 78613-1419 | VISA/MC accepted. NT-based sites, be sure to
Fax/Voice +1(512)378-3246 | read details of WFTPD Pro for NT.
------------------------------
From: William Hugh Murray <[EMAIL PROTECTED]>
Reply-To: [EMAIL PROTECTED]
Crossposted-To: alt.security,comp.security,alt.2600
Subject: Re: The Kingdom of God
Date: Tue, 20 Feb 2001 14:33:28 GMT
Jashter wrote:
> Yeah, but then you must wonder if there really is a god in the first
> place...
No, I really do not. I do wonder, in the sense that the creation is wonder
full. I wonder at the flowers and the trees. I wonder at the miracle of life.
I wonder at man and his works. I delight in it all, particularly in infants. I
wonder that the earth should be just the right distance from the sun and that
the moon should be just the right distance from the earth. I wonder at the
immensity of time and space and how tiny is a quark. I wonder at the nature
of creation and its relation to the creator. I am certainly in constant and
perpetual awe. However, one should not confuse that wonder, that awe, with
existential doubt.
God is manifest and quite obvious to me, impossible to ignore. There is more
evidence of God than I can begin to comprehend in one short lifetime. It is the
full comprehension, the understanding, that is the problem. That others can
raise theological questions that I cannot answer to my satisfaction is not a
source of doubt, only evidence of my ignorance and other limitations. On the
other hand, if I thought that I knew all the answers, or even that they were
knowable, then the mystery, the wonder, the awe, and the delight might be gone.
I apologize to you all for the off-topic discourse but I thank Jashter for
reminding me just how much I do delight in the gift of life.
> "William Hugh Murray" <[EMAIL PROTECTED]> wrote in message
> news:[EMAIL PROTECTED]...
> > "Trevor L. Jackson, III" wrote:
> > > > Yes. And your security point is what? In any case, by definition,
> > > > God's will is done.
> > >
> > > This thesis (sorry) implies that resistance to god's will is futile, and
> > > reduces most theological texts (Book of Mormon, Koran, Bible, etc.) into
> > > attitude adjustments. Whither free will?
> > >
> > > The presumed congruence between divine and human wills makes the
> precedence
> > > ambiguous. Just who is the willer and who is the willee, god or the
> human?
> >
> >
> > Did you ever think about the lyrics of the song "If I ruled the world?"
> > Do you remember the line in the movie "Oh God" in which God says, "I
> > never figured out how to make something with an inside and no outside,"
> > or, "I made math too hard." How about St. Anselm's proof for the
> > existence of God?
> >
> > Let us not forget where this thread began and start to take it too
> > seriously. However, I do not think that the positions are
> > irreconcilable. If there is free will for man, it is because God
> > consents to it. Man did not create it and could not rebel without the
> > freedom to do so. If God consents to it, then, by definition, it is
> > God's will. If God is anything like Markku J. Saarelainen
> > <[EMAIL PROTECTED]> seems to think of him/her as being, then
> > he/she does not have to consent to free will for man if he/she does not
> > want to. This is of course the inconsistency in the position that
> > started the thread. Indeed, it is the central problem of that theology
> > that wants to portray God as all loving and good and wants to put all
> > the responsibility for evil in the world on man or Satan. I do not
> > pretend to know the answer but I can certainly appreciate the question.
------------------------------
From: [EMAIL PROTECTED] (Dave Seaman)
Crossposted-To: sci.math
Subject: Re: Given any arbitrary numbers a and b. Can I ALWAYS find a transcendental
number between a and b?
Date: 20 Feb 2001 09:43:09 -0500
In article <[EMAIL PROTECTED]>,
John Savard <[EMAIL PROTECTED]> wrote:
>What is
>the name of the property of having measure n over a line segment of
>length n?
You can say that a property holds almost everywhere, or that almost all real
numbers are transcendental.
--
Dave Seaman [EMAIL PROTECTED]
Amnesty International calls for new trial for Mumia Abu-Jamal
<http://www.amnestyusa.org/abolish/reports/mumia/>
------------------------------
From: John Myre <[EMAIL PROTECTED]>
Subject: Re: CipherText patent still pending
Date: Tue, 20 Feb 2001 08:19:20 -0700
Benjamin Goldberg wrote:
<snip>
> Yes. However, I would be rather curious to see how we could prove that
> P=NP, but still lack an algorithm for solving NP problems in P time.
Well, sure, so would we all. But non-constructive proofs
occur all the time. Consider, for example, the proof that
there are an infinite number of primes: you can't use it
to find primes!
> Although there were a number of problems with it, there was a paper
> (less than a year ago, IIRC) which claimed you could solve some type of
> NPC graph problem in O(N^6) time.
<snip>
If that claim is true, then the paper has the proof that
P = NP, by definition. Therefore, I suspect the paper
(or your recollection) is wrong.
JM
------------------------------
** FOR YOUR REFERENCE **
The service address, to which questions about the list itself and requests
to be added to or deleted from it should be directed, is:
Internet: [EMAIL PROTECTED]
You can send mail to the entire list by posting to sci.crypt.
End of Cryptography-Digest Digest
******************************
