Cryptography-Digest Digest #614, Volume #13 Fri, 2 Feb 01 15:13:01 EST
Contents:
Re: Q: Base64 mapping (William Stallings)
Re: A story of distrust .... my ex-mother, Eeva Nuora, Varkaus, Finland (StanMann)
Re: New checksum algorithm (Robert Scott)
Re: Tree algorithm ("Stefan Habenschuss")
Re: Some Cryptogram deciphering help (Derek Bell)
Re: fast signing ("Tom Schmidt")
Re: On combining permutations and substitutions in encryption (Darren New)
Re: Most secure code for US Citizen. ("Douglas A. Gwyn")
Re: Most secure code for US Citizen. ("Douglas A. Gwyn")
The prospects for a theoretical breakthrough in the factoring problem
([EMAIL PROTECTED])
Re: The prospects for a theoretical breakthrough in the factoring problem (Bob
Silverman)
Re: CipherText patent still pending (Paul Crowley)
Re: New checksum algorithm (Dido Sevilla)
Re: On combining permutations and substitutions in encryption ("Douglas A. Gwyn")
Re: On combining permutations and substitutions in encryption ("Douglas A. Gwyn")
Re: fast DES implementation for 64-bit (alpha) architecture ("Joseph Ashwood")
Re: CipherText patent still pending ("Prichard, Chuck")
Re: Some Cryptogram deciphering help (Tom St Denis)
Re: Where is the encryption hardware? ("Joseph Ashwood")
Re: The prospects for a theoretical breakthrough in the factoring problem ("Joseph
Ashwood")
Re: On combining permutations and substitutions in encryption ("Joseph Ashwood")
----------------------------------------------------------------------------
From: [EMAIL PROTECTED] (William Stallings)
Subject: Re: Q: Base64 mapping
Date: Fri, 02 Feb 2001 11:34:08 -0500
In article <95ejei$f63$[EMAIL PROTECTED]>, "Manuel Pancorbo"
<[EMAIL PROTECTED]> wrote:
> Where can I find this information?
>
> I imagine that Base64 is based in transforming three 8-bit words onto four
> 6-bit numbers, and mapping these numbers in printable manner.
>
> There are two 26-set of letters plus one 10-set of numbers, this yields 62
> possible printable characters, plus characters "+" and "/" up to 64
> characters needed. But, what is the exact mapping? 0 -> "+", 1 -> "/", 2 ->
> "0", and so on?
>
>From RFC 2045, The MIME spec:
Value Encoding Value Encoding Value Encoding Value Encoding
0 A 17 R 34 i 51 z
1 B 18 S 35 j 52 0
2 C 19 T 36 k 53 1
3 D 20 U 37 l 54 2
4 E 21 V 38 m 55 3
5 F 22 W 39 n 56 4
6 G 23 X 40 o 57 5
7 H 24 Y 41 p 58 6
8 I 25 Z 42 q 59 7
9 J 26 a 43 r 60 8
10 K 27 b 44 s 61 9
11 L 28 c 45 t 62 +
12 M 29 d 46 u 63 /
13 N 30 e 47 v
14 O 31 f 48 w (pad) =
15 P 32 g 49 x
16 Q 33 h 50 y
| | Descriptions, errata sheets and discount order info |
| | for my current books and info on forthcoming books: |
| Bill Stallings | WilliamStallings.com |
| [EMAIL PROTECTED] | |
| | Visit Computer Science Student Support site: |
| | WilliamStallings.com/StudentSupport.html |
------------------------------
From: StanMann <[EMAIL PROTECTED]>
Reply-To: [EMAIL PROTECTED]
Crossposted-To: alt.2600,alt.security,comp.security
Subject: Re: A story of distrust .... my ex-mother, Eeva Nuora, Varkaus, Finland
Date: Fri, 02 Feb 2001 16:51:01 GMT
"Markku J. Saarelainen" wrote:
>
> Basically, this the story of distrust.
>
<snip>
This is relavent to any of the groups you posted this too??
Fascinating story, should I care?
StanMann
------------------------------
From: [EMAIL PROTECTED] (Robert Scott)
Subject: Re: New checksum algorithm
Reply-To: [EMAIL PROTECTED]
Date: Fri, 02 Feb 2001 17:07:58 GMT
On Fri, 02 Feb 2001 13:23:13 GMT, [EMAIL PROTECTED] (Sami J. M�kinen) wrote:
><[EMAIL PROTECTED]>:
>>>I decided to design my first checksum algorithm (for non-crypto purpose),
>>In what way is your checksum better (for non-crypto apps)
>>than the old-fashioned:
>>for ( i = 0; i < n; i++ )
>>{
>> sum = sum + buffer[i];
>>}
>>return sum;
>>..which would be even faster yet?
>
>1,1,2 = 2,1,1 = 2,2 and 4, all of those have the same checksum, or
>are just being ironic?
No, I really wanted to know what requirements your app had that
favored your somewhat more complicated checksum. Your example
of 1,1,2 = 2,1,1 is a good one if one of the purposes of your
checksum is to check for items being switched around in the
buffer into a different order. Obviously the simple checksum
I proposed would not detect this change while it seems your
original idea would.
Sometimes people want to detect a single burst error of a certain
length, or perhaps detect any change that involves less than
"n" bits. These requirements lead to different checksums or CRCs.
For serial communications over a noisy line, for example,
permutations of input items is not particularly likely. In fact,
I can't think of any naturally-occurring setting (other than
intelligent tampering) where permutation of items is likely.
Robert Scott
Ypsilanti, Michigan
(Respond through newsgroups, not by direct e-mail.)
------------------------------
From: "Stefan Habenschuss" <[EMAIL PROTECTED]>
Subject: Re: Tree algorithm
Date: Fri, 02 Feb 2001 17:14:15 GMT
> I'm interested in an algorithm which search through a tree for a special
>
> value and then returns the "cheepest" way there.
> The root is 1 and then there is 2 ways to go
So what you have is a binary tree.
> , one (right) increases the
>
> value with 4 and the other (left) multiplicates it with 3.
> It costs 10 to go left and 5 to go right.
>
> Tree(int value, int search, int sum){
>
> if(display==search)
> return sum;
>
> if(display>search)
> return 0;
>
> Tree(value*3, search, sum+10);
> Tree(value+4, search, sum+5);
> }
>
Why don't you return the value of your recursive calls like that?
int retsum;
if((retsum = Tree(value*3, search, sum+10)) || (retsum = Tree(value+4,
search, sum+5)))
return retsum;
> The function can be invoked like this: Tree(1,109,0), then value=1,
> search=109, sum=0.
> This function is only going left as long as poosible and then right,
> what I need to do is test ALL possible ways.
This is what it will do actually. Maybe you want a breadth first search
algorithm, which first evaluates all the sums in the same depth, so it
basically runs like this:
1
2 3
4 5 6 7
...
The implementation of this is a little more complicated than depth first
search...
> I'm not asking you to solve this, but I'd be happy to get any tips.
>
> Thanks in advance.
>
Hope this helps...
------------------------------
From: Derek Bell <[EMAIL PROTECTED]>
Subject: Re: Some Cryptogram deciphering help
Date: 2 Feb 2001 18:08:52 -0000
Todd Luther <[EMAIL PROTECTED]> wrote:
: I have this following quotation that is encoded and I could use some
: assistance....I have tried a monoalphabetic decryption, the Vigenere table,
: a columnar, and upto a 3 alphabet polyalphabetic subsitution with no
: solution still....can anyone help me?
: pbegu uymiq icuuf guuyi qguuy qcuiv fiqgu uyqcu qbeme vp
Have you tried Beaufort or variant Beaufort?
(See http://www.und.nodak.edu/org/crypto/crypto/.chap08.html if you're
not sure what they are.)
Derek
--
Derek Bell [EMAIL PROTECTED] |"Usenet is a strange place."
WWW: http://www.maths.tcd.ie/~dbell/index.html| - Dennis M Ritchie,
PGP: http://www.maths.tcd.ie/~dbell/key.asc | 29 July 1999.
|
------------------------------
Reply-To: "Tom Schmidt" <[EMAIL PROTECTED]>
From: "Tom Schmidt" <[EMAIL PROTECTED]>
Subject: Re: fast signing
Date: Fri, 02 Feb 2001 18:36:15 GMT
"Joseph Ashwood" <[EMAIL PROTECTED]> wrote in message
news:elkxOTLjAHA.276@cpmsnbbsa07...
> Ok, I was going to reply, but a little test of mine just finished. I can
now
> state rather forcefully that on the system I am on right now 10K sig/s
can't
> be done regardless of how fast the algorithm is. I just tested the
bandwidth
> to disk, I can write about 12000 entries per second to the disk (without
any
> hashing or signing occuring). So I think I've reached a suitable remedy,
we
> absolutely must reduce the speed requirement. So as of right now it
stands:
> ECDSA
> ESIGN
> NSS (response recieved in private see ntru.com for details, claim of 0.5
ms
> per sig)
> QUARTZ
>
> seem to be the best bets for software.
>
> For hardware RSA seems to be everyone's (meaning the designers) favorite
> Rainbow Cryptoswift seems to peek at 1000 private key ops/second
> nCipher does 300, but can be combined together to get 2000/sec
>
> Those seem to be the two fastest, am I missing anybody important?
> Joe
>
I have been following the discussion engehtered by the original posting by
Mr. Ashwood:
"I need signing to be excessively fast. I've gon an application where
one person here expects in the 10,000 signature/second range (I
doubt he'll get that speed out of his code, but that's another issue),
on a single-processor x86 P4 1.5GHz, gobs of RAM, etc."
and the recent summary by Mr. Ashwood:
"...So as of now it stands:
ECDSA
ESIGN
NSS (private response - see ntru.com for details, claim of
0.5 milliseconds per sig)
QUARTZ
..."
The NSS alternative (third in the list above) is the signature comnponent
that is part of the NTRU PKI. NTRU (NSS) generates signatures at
strength equivalent to RSA 1024 or ECC 163 at about 3200 sig/sec
and the same rate of verifications per second on an 800 MHz P3
system. For Mr Ashwood's very speedy (1.5GHz) system this would
translate to about 6,000 signatures per second.
Of course as is apparent, there are other bottlenecks (I/O in this case)
that would get in the way of his goal of 10,000 transactions/second.
NTRU does offer some advantages however. Since signatures are so
speedy they do not hog the machine in a compute intensive state. If
the entire transaction consists of a digest creation, signature, and
write, the signature component is small compared to the other parts.
Jim Kotanchik
VP of Engineering, NTRU
[EMAIL PROTECTED]
Tom Schmidt
Consulting Engineer, NTRU
[EMAIL PROTECTED]
>
consists of a digest creation, signature, and write, the
signature component is small compared to the other parts.
Jim Kotanchik
VP of Engineering, NTRU
[EMAIL PROTECTED]
------------------------------
From: Darren New <[EMAIL PROTECTED]>
Subject: Re: On combining permutations and substitutions in encryption
Date: Fri, 02 Feb 2001 18:41:00 GMT
Paul Crowley wrote:
> FWIW I'd argue that Travelling Salesman Problem is by far the best
> known;
Ah yes, the travelling salesman problem, which has befuddled computer
scientists for decades, but which travelling salesmen have been solving for
centuries. ;-)
--
Darren New / Senior MTS & Free Radical / Invisible Worlds Inc.
San Diego, CA, USA (PST). Cryptokeys on demand.
Ignorance can be cured. Naivety cures itself.
------------------------------
From: "Douglas A. Gwyn" <[EMAIL PROTECTED]>
Subject: Re: Most secure code for US Citizen.
Date: Fri, 2 Feb 2001 17:50:38 GMT
Jakob Jonsson wrote:
> Maybe this is your opinion, but as far as I know, the best known attack
> against any of these ciphers is a brute-force search through the entire key
> space. Regarding Rijndael, one may have some concerns about its relatively
> small "security margin" (whatever that is supposed to mean). Yet, we don't
> know anything about how much we gain in security from adding extra rounds to
> a cipher already resistant to all known attacks. Maybe one extra round in
> Rijndael adds to security as much as 10 extra rounds in Serpent. Maybe it
> doesn't, but we don't know. It is impossible to predict future advances in
> cryptanalysis.
Hear hear!
------------------------------
From: "Douglas A. Gwyn" <[EMAIL PROTECTED]>
Subject: Re: Most secure code for US Citizen.
Date: Fri, 2 Feb 2001 18:02:13 GMT
Michael Robbins wrote:
> I'd like to provide as much protection against reverse engineering as I
> can while limiting the impact on my productivity.
> ...
> I'm not quite sure the protection is worth the effort. It certainly
> seems like a great deal of work.
There is of course supposed to be *legal* protection against
reverse engineering. For *legal* reasons, you might want to
use some simple encryption mehod to "protect" your files in
order to show a potential court that you made an effort at
protecting your files. Something like UNIX "crypt" would
suffice for such a purpose. (Note that it is by no means
secure against cryptanalysis.)
If, as you postulate, your adversary is well equipped to
perform cryptanalysis, your only hope would be to use some
method for which its successful cryptanalysis would be big
news, e.g. AES. That way if you do find that your files
have been stolen, at least you have contributed something
useful to the state of public knowledge about cryptology.
As far as protecting against other analysis channels such
as disk files, etc. there is a practical limit. If you're
using a system adminstered by someone else, how to you know
that there is not a keyboard snooper copying everything
that you type, including crypto password? Swap files can
be a major loophole, since they contain images of running
process data (which must be unencrypted to be useful).
While there *are* secured operating systems, unless you
bring it with you you can't be sure you're using one.
------------------------------
From: [EMAIL PROTECTED]
Subject: The prospects for a theoretical breakthrough in the factoring problem
Date: Fri, 02 Feb 2001 18:45:04 GMT
What are the prospects for a theoretical breakthrough in the factoring
problem (or a proof that factoring is difficult)?
I know that this is a very difficult question because a breakthrough
can without premonition � a sudden flash of genius is enough. But
perhaps somebody here can make an advanced guess.
And what�s the general opinion among �the experts�?
Which efforts have been done in the past? As far as I know many
mathematicians have tried the last 200 years but failed.
My interest to this is related to the RSA so is a new factoring
algorithm together with the computer development more likely to make it
(practically) possible to factorise large integers?
Or will maybe the quantum computer come first??
//Sulfolobious
Sent via Deja.com
http://www.deja.com/
------------------------------
From: Bob Silverman <[EMAIL PROTECTED]>
Subject: Re: The prospects for a theoretical breakthrough in the factoring problem
Date: Fri, 02 Feb 2001 18:54:00 GMT
In article <95ev7c$dnp$[EMAIL PROTECTED]>,
[EMAIL PROTECTED] wrote:
>
>
> What are the prospects for a theoretical breakthrough in the factoring
> problem (or a proof that factoring is difficult)?
> I know that this is a very difficult question because a breakthrough
> can without premonition
It isn't a difficult question, it is an IMPOSSIBLE question.
Unless, of course, you happen to have a crystal ball....
--
Bob Silverman
"You can lead a horse's ass to knowledge, but you can't make him think"
Sent via Deja.com
http://www.deja.com/
------------------------------
Subject: Re: CipherText patent still pending
From: Paul Crowley <[EMAIL PROTECTED]>
Date: Fri, 02 Feb 2001 19:01:39 GMT
"Prichard, Chuck" <[EMAIL PROTECTED]> writes:
> Generally saying that an algorithm has no value if it is either symmetric
> or asymmetric goes against logic in view of the fact that once
> implemented, anything can be of use and value.
I have implemented a paperweight. Details to follow.
--
__
\/ o\ [EMAIL PROTECTED]
/\__/ http://www.cluefactory.org.uk/paul/
------------------------------
From: Dido Sevilla <[EMAIL PROTECTED]>
Subject: Re: New checksum algorithm
Date: Sat, 03 Feb 2001 02:55:58 +0800
"Sami J. M=E4kinen" wrote:
> =
> I decided to design my first checksum algorithm (for non-crypto purpose=
),
> I hope you don't mind posting it here since this should not be far off
> topic.
> =
> The goal was to have extremely high speed in 32-bit Pentium platform.
> =
Other than this, what were you trying to achieve? If you set out to
create an error detection code, similar to CRC32, try to see what
happens to your checksum when you have a one-bit error. Try to write
down your equations as boolean expressions (note that addition is XOR
with carry propagation, and a multiplication can be reduced to a set of
additions), and expand it out for an unspecified input value. See what
happens to your expression when any one of the bits of your unspecified
input value is replaced by its inverse. If the symbolic expansions are
the same for some bit positions for the NOT, well, I guess you must have
a problem. You can't detect some one-bit errors.
--
Rafael R. Sevilla <[EMAIL PROTECTED]> +63 (2) 4342217
ICSM-F Development Team, UP Diliman +63 (917) 4458925
OpenPGP Key ID: 0x0E8CE481
------------------------------
From: "Douglas A. Gwyn" <[EMAIL PROTECTED]>
Subject: Re: On combining permutations and substitutions in encryption
Date: Fri, 2 Feb 2001 18:10:14 GMT
Mok-Kong Shen wrote:
> ... My guess is that applying stuffs in direction of fuzzy
> logic wouldn't be much appreciated in the field of crypto,
> where one wants in general to have fairly exact numerical
> quantities, not wide ranges, not to say something 'estimated'.
Actually, fuzzy logic can be quite useful in cryptanalysis.
Jim Reeds (with Dennis Ritchie and Robert Morris) wrote a
paper in 1978 that applied what was essentially a fuzzy
logic approach to cryptanalysis of Hagelins, turning it
into an eigenvalue problem. The paper was not published,
out of concern about possibly tipping off Hagelin users
(in some third-world countries for example) that their
systems were more vulnerable than they had realized, which
could have had an effect on our national security.
------------------------------
From: "Douglas A. Gwyn" <[EMAIL PROTECTED]>
Subject: Re: On combining permutations and substitutions in encryption
Date: Fri, 2 Feb 2001 18:15:28 GMT
Matt Timmermans wrote:
> ... can be converted into a SAT problem instance ...
Has it been shown that the process of conversion itself
runs in polynomial time?
------------------------------
From: "Joseph Ashwood" <[EMAIL PROTECTED]>
Subject: Re: fast DES implementation for 64-bit (alpha) architecture
Date: Fri, 2 Feb 2001 11:07:44 -0800
<[EMAIL PROTECTED]> wrote in message
news:95cude$n5o$[EMAIL PROTECTED]...
> Does anyone have any C code that is optimized for the Dec Alpha 64-bit
> processors?
Not onhand, but the distributed.net code did in fact use the fast DES code
for the Alpha. If you can't get ahold of it tell me I may have a copy lying
around on my alpha at home.
Joe
------------------------------
From: "Prichard, Chuck" <[EMAIL PROTECTED]>
Subject: Re: CipherText patent still pending
Date: Fri, 02 Feb 2001 19:45:46 GMT
The previous post has been edited and appears on my PWS which can be
accessed when I am online by using either of the links below. The
algorithm description is accurate.
It is the algorithm that has been implemented in both the simple Private
Email (javascript/unmasked)demonstration and the Page-Tag-Encryption
(masked) used by the Perl site wrapper.
It should be noted that the algorithm has features to build the needed
attribute,modified key, offset, and mask prior to recursive ciphering of
a large number of small strings. The idea behind query string encryption
is that any value that is found not to matchup with something in the
lookup table, is invalid possibly as the result of tampering. The
algorithm for authentication is quite simplified when encryption is
applied to the query string.
Charles Prichard
http://greentv.crosswalkcentral.com -PWS referral
http://members.nbci.com/chuck_prichard -PWS referral
------------------------------
From: Tom St Denis <[EMAIL PROTECTED]>
Subject: Re: Some Cryptogram deciphering help
Date: Fri, 02 Feb 2001 19:44:10 GMT
In article <955443$la9$[EMAIL PROTECTED]>,
"Todd Luther" <[EMAIL PROTECTED]> wrote:
> I have this following quotation that is encoded and I could use some
> assistance....I have tried a monoalphabetic decryption, the Vigenere table,
> a columnar, and upto a 3 alphabet polyalphabetic subsitution with no
> solution still....can anyone help me?
>
> pbegu uymiq icuuf guuyi qguuy qcuiv fiqgu uyqcu qbeme vp
It says
"I am a stupid luser and My mother would be ashamed, I should go stick my
head in some ice for 30 years".
Tom
Sent via Deja.com
http://www.deja.com/
------------------------------
From: "Joseph Ashwood" <[EMAIL PROTECTED]>
Subject: Re: Where is the encryption hardware?
Date: Fri, 2 Feb 2001 11:40:41 -0800
I'm not convinced that the secure key exchange would be time costly. What
you do is you make several grades of memory in phones and use EC-DH, with
fixed parameters and a key pair that is fixed per phone (identified by phone
number). Store all the recent calls public key in memory (you could even
store the symmetric key instead). Normally a person will call/be called by
one of a few people, so most phones would only need room to store 16 phone
keys, with 163-bit ECC that's not even a KB, of course you'd have to store a
mapping number, so double is, it's around 1/2 KB. use the other 1/2KB of RAM
to compute the current key. When connecting to a phone you add a few rounds
of the who are you game. When connecting to a known phone the computation is
done before connection, when dialing a new phone the computation is down
while connected. It would be easy to make phones that could store thousands
or even millions of keys (ref IBM recent announcement of a 30GB minidrive).
So it's very doable in terms of RAM, and you tack on a processor for
Rijndael, or 3DES or ARC4 or .. . . . . It really wouldn't be a costly
connection. 1KB of SRAM can be bought for a few cents in bulk, Rijndael
doesn't take many gates, it would be dwarfed by the 60,000 transistors for
the RAM, as long as you're fixing the public and private keys per phone,
probably by storing the private key and generating the public key at
startup, that can be done in an extra KB of RAM fairly quickly. All in all
you'd be looking at something certainly less complicated than a 486.
Considering the target an ARM processor would be a prime candidate (low
pwer, relatively cheap, and it's a full processor). Of course you'd lose
some battery life but that could be helped by only spinning the drive up
right before reading it, and spinning down right after.
Come to think of it, it may be possible to eliminate the drive altogether,
we already have Web enabled phones, and the public keys are non-sensitive so
they can be broadcast openly. What you do is before dialing the phone
requests the public key for phone ID #K (if known), and waits for the
response, if no response is forthcoming, dial the phone and request it
personally (through the who are you game). This eliminates the need to have
a hard drive at all.
This might be a worthwhile examination. I guess I'll think about it over the
weekend and see what I come up with.
Joe
------------------------------
From: "Joseph Ashwood" <[EMAIL PROTECTED]>
Subject: Re: The prospects for a theoretical breakthrough in the factoring problem
Date: Fri, 2 Feb 2001 11:46:43 -0800
<[EMAIL PROTECTED]> wrote in message
news:95ev7c$dnp$[EMAIL PROTECTED]...
> What are the prospects for a theoretical breakthrough in the factoring
> problem (or a proof that factoring is difficult)?
Impossible to answer absolutely but the trend of late has been every 5 years
or so a new factoring algorithm arrives, however looking back further the
time between discovories has been decreasing, so I'd guess at the 50% point
being within 2 years today. It's just a guess though so don't place any
money on it.
> As far as I know many
> mathematicians have tried the last 200 years but failed.
Actually it's much closer to 2000 years. And it's not that they've failed,
one of them may have come across the answer but took one look at how long it
took to factor the number 4 and decided not to bother writing it down
> My interest to this is related to the RSA so is a new factoring
> algorithm together with the computer development more likely to make it
> (practically) possible to factorise large integers?
> Or will maybe the quantum computer come first??
I'd still put some money on the next factoring algorithm not breaking
(properly selected) 1024-bit RSA keys, but I'd put a lot more money on 2048
or 4096-bit keys.
Joe
------------------------------
From: "Joseph Ashwood" <[EMAIL PROTECTED]>
Subject: Re: On combining permutations and substitutions in encryption
Date: Fri, 2 Feb 2001 11:54:08 -0800
"Douglas A. Gwyn" <[EMAIL PROTECTED]> wrote in message
news:[EMAIL PROTECTED]...
> Matt Timmermans wrote:
> > ... can be converted into a SAT problem instance ...
>
> Has it been shown that the process of conversion itself
> runs in polynomial time?
I don't think it's really a necessary determination, however that result
would be useful in proving the more important result of it taking no more
than SAT time. Assuming that the conversion takes no more than SAT time, it
proves is that SAT at least as hard as the hardest problem in NP.
Joe
------------------------------
** 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
******************************
