Cryptography-Digest Digest #766, Volume #11 Sat, 13 May 00 16:13:01 EDT
Contents:
Even more cryptanalysis requested: lja2 (Andru Luvisi)
Re: Prime Generation in C,C++ or Java (Jerry Coffin)
security ([EMAIL PROTECTED])
Re: security (Tom McCune)
Re: factor large composite (Tim Tyler)
Re: Question regarding authentication implementation (Abid Farooqui)
incremental prng? ([EMAIL PROTECTED])
Re: Question regarding authentication implementation (Anne & Lynn Wheeler)
Re: Theoretical question (RaeNye)
Re: Prime Generation in C,C++ or Java (Wei Dai)
----------------------------------------------------------------------------
From: Andru Luvisi <[EMAIL PROTECTED]>
Subject: Even more cryptanalysis requested: lja2
Date: 13 May 2000 09:18:00 -0700
lja2 is based on the same concept as lja1, but using the mixing of
operations from different algebraic groups as a nonlinear transform,
and a plain old random number as a key. My gut tells me that lja2 is
not as strong as lja1, but I'm not sure. Here it is:
/*
lja2 encryption software by Andru Luvisi
Copyright (C) 2000 Andru Luvisi
This program is free software; you can redistribute it and/or modify
it under the terms of the GNU General Public License as published by
the Free Software Foundation; either version 2 of the License, or
(at your option) any later version.
This program is distributed in the hope that it will be useful,
but WITHOUT ANY WARRANTY; without even the implied warranty of
MERCHANTABILITY or FITNESS FOR A PARTICULAR PURPOSE. See the
GNU General Public License for more details.
You should have received a copy of the GNU General Public License
along with this program; if not, write to the Free Software
Foundation, Inc., 675 Mass Ave, Cambridge, MA 02139, USA.
*/
void lja2_encrypt(unsigned char *key, int keylen,
unsigned char *block, int blocksize,
int cycles)
{
unsigned char acc, data_byte, key_byte;
int round, rounds, i;
rounds = blocksize * cycles;
for(round = 1; round <= rounds; round++)
{
for(i = 0, acc = round; i < blocksize - 1; i++)
{
data_byte = block[(i + round) % blocksize];
key_byte = key[(i + round/3) % keylen];
acc += ((acc ^ data_byte) + key_byte + i) ^ round;
}
block[(i + round) % blocksize] ^= acc;
}
}
void lja2_decrypt(unsigned char *key, int keylen,
unsigned char *block, int blocksize,
int cycles)
{
unsigned char acc, data_byte, key_byte;
int round, rounds, i;
rounds = blocksize * cycles;
for(round = rounds; round >= 1; round--)
{
for(i = 0, acc = round; i < blocksize - 1; i++)
{
data_byte = block[(i + round) % blocksize];
key_byte = key[(i + round/3) % keylen];
acc += ((acc ^ data_byte) + key_byte + i) ^ round;
}
block[(i + round) % blocksize] ^= acc;
}
}
Thoughts?
Andru
--
==========================================================================
| Andru Luvisi | http://libweb.sonoma.edu/ |
| Programmer/Analyst | Library Resources Online |
| Ruben Salazar Library |-----------------------------------------|
| Sonoma State University | http://www.belleprovence.com/ |
| [EMAIL PROTECTED] | Textile imports from Provence, France |
==========================================================================
------------------------------
From: Jerry Coffin <[EMAIL PROTECTED]>
Subject: Re: Prime Generation in C,C++ or Java
Date: Sat, 13 May 2000 11:39:59 -0600
In article <RrdT4.39731$[EMAIL PROTECTED]>,
[EMAIL PROTECTED] says...
> Bryan Olson <[EMAIL PROTECTED]> wrote:
> > First, and beside the original point, there's the
> > constructor-abuse resulting in the prime generator being
> > called "BigInteger". Should it be obvious that the way to
>
> The problem is that isProbablePrime must be in BigInteger, since it's
> reasonable to ask if an integer is prime. A BigPrime class would then
> contain only the single constructor. Even worse, you would have to
> either double the number of methods in BigInteger, or typecast
> BigPrime every time you wanted to do arithmetic involving both primes
> and composites.
This is getting a lot more into the class design than anything
directly related to cryptography, but I don't see any of the above
being true at all. A BigPrime is always a BigInteger. Anything that
works on a BigInteger should always be able to use a BigPrime as
well. IOW, BigInteger satisfies the Liskov Substitution Principle.
It can and almost certainly should be derived from BigInteger. Since
it's a direct derivative, the compiler can convert a BigPrime to a
BigInteger whenever needed, and no extra operators or explicit
typecasts are needed.
In most cases, using the BigInteger mathematical operators gives the
"right" result as well: they produce BigIntegers, not BigPrimes. If
you multiply two BigPrimes, they should obviously produce a
BigInteger as the result. If you use a BigPrime in addition,
subtraction or division, the result _might_ be a prime as well, but
it's up to you whether that matters to you. If it does, you can test
it and find out, but if it doesn't, you simply leave the result as a
BigInteger, which is what the operator would obviously produce as a
default.
In short, this is nearly a perfect example of a situation in which
derivation is the right thing to do, and (at least assuming Java
hasn't done something really stupid to mess up what C++ would do in
the same situation) essentially everything the language does by
default will end up being correct.
At least in C++, I can see only one thing that would be nice here:
the ability to overload dynamic_cast, which would allow you to test
whether the number represented by a BigInteger was really a prime or
not, and produce the right result from a dynamic_cast based on that.
This is a _slightly_ different thing than dynamic_cast normally does,
but I think the intent is similar enough that it would be a useful
thing to be able to do -- I may attempt to bring it up as a
discussion in the appropriate newsgroup, unless somebody points out a
major problem with the idea.
--
Later,
Jerry.
The universe is a figment of its own imagination.
------------------------------
From: [EMAIL PROTECTED]
Subject: security
Date: Sat, 13 May 2000 17:41:17 GMT
I have recently come to figure that I really need to have my data out
of the hands of people who do not need to see my stuff.
There seems to be two products. PGP and Blowfish. Can anybody tell me
the difference between the two, which oneprovides more security as far
as some one being able to break the code and read my stuff, I mean real
smart people.
Any suggestion is appreciated.
WS
Sent via Deja.com http://www.deja.com/
Before you buy.
------------------------------
From: Tom McCune <[EMAIL PROTECTED]>
Subject: Re: security
Date: Sat, 13 May 2000 18:18:28 GMT
=====BEGIN PGP SIGNED MESSAGE=====
In article <8fk43r$5ic$[EMAIL PROTECTED]>, [EMAIL PROTECTED] wrote:
>I have recently come to figure that I really need to have my data out
>of the hands of people who do not need to see my stuff.
>
>There seems to be two products. PGP and Blowfish. Can anybody tell me
>the difference between the two, which oneprovides more security as far
>as some one being able to break the code and read my stuff, I mean real
>smart people.
>
>Any suggestion is appreciated.
Blowfish is a symmetric encryption algorithm, while PGP is encryption
software using several encryption algorithms. Although Blowfish has a
rather good reputation, it is not one of the algorithms used by PGP.
=====BEGIN PGP SIGNATURE=====
Version: PGP Personal Privacy 6.5.3
Comment: My PGP Page & FAQ: http://www.McCune.cc/PGP.htm
iQCVAwUBOR2cjMMxrQ5/VTwtAQE1xAP/TbLaqkdsAAFpJAl9G0piNW+OI+G0+T9K
pLD4+H7svEQ1pYMejtZTRS8zhSq9uQS/1uLr4xmmhlUmEOoojUqW+n9yzDoesxo1
4UQ/6b82YePA01U4uUCrvXSkQRViOrgvSyNhvl/zT7djjkgCPMaUZ8AGpht9bpRX
ocq1yilrtFQ=
=lPdr
=====END PGP SIGNATURE=====
------------------------------
From: Tim Tyler <[EMAIL PROTECTED]>
Subject: Re: factor large composite
Reply-To: [EMAIL PROTECTED]
Date: Sat, 13 May 2000 17:52:51 GMT
Stanley Chow <[EMAIL PROTECTED]> wrote:
: As Dann Corbit explained in his article, God's algorithm is quite
: well known and fast. Is there any variant of quantum algorithm
: that is O(1)?
Not even God's algorithm is O(1). God's algorithm requires a gigantic
look-up table. Gigantic look-up-tables take up space, and take time to
access. It's not even clear that it's the fastest method of determining
primality on all scales.
--
__________ Lotus Artificial Life http://alife.co.uk/ [EMAIL PROTECTED]
|im |yler The Mandala Centre http://mandala.co.uk/ Be good, do good.
------------------------------
From: Abid Farooqui <[EMAIL PROTECTED]>
Subject: Re: Question regarding authentication implementation
Date: Sat, 13 May 2000 18:24:54 GMT
Oops ... my bad, what I wanted to say is:
Actually the cert queue will have both the CA keys as well as partner
certificates and there is NO automatic refresh of certificates every day or two
like you mentioned.
I mistakenly omitted the NO in my last message.
Thanks
Abid
Abid Farooqui wrote:
> Dear Mr. Denis,
> Thanks for the prompt reply.
> Actually the cert queue will have both the CA keys as well as partner
> certificates and there is automatic refresh of certificates every day or two
> like you mentioned. One would have to delete the partner certificates and
> reload them again, manually verifying all the certs against the CA
> certificates.
> On the second note, the CA certificates will be from VeriSign, Thawte and
> may be other similar CAs not an intranet situation at all. Actually bulk of
> the data transfers and connections will be made using the internet.
> Given these facts what do you think?
> Thanks
> Abid Farooqui
>
> Tom St Denis wrote:
>
> > In article <[EMAIL PROTECTED]>,
> > Abid Farooqui <[EMAIL PROTECTED]> wrote:
> > > I have an interesting scenario for you guys to battle over. I myself
> > > cannot make up my mind for sure but lean towards a certain position in
> > > this.
> > > Here goes ...
> > > A colleague of mine has developed using BSAFE libraries a security
> > > application that does authentication at connection startup and
> > > encryption when data is transferred. The client certificates, Root
> > > certificates and client or partner certificates are stored in so
> > called
> > > queue. When you load a client/partner certificate you can VERIFY that
> > > certificate against a list of available CA Root certificates that you
> > > already have in the queue. This is a completely separate step and is
> > > done in a non-active manner, meaning this happens way before the
> > > client/partner is establishing any kind of connection to you.
> > > Now, that you have a clinet/partner certificate loaded into a
> > queue ...
> > > when the client/partner establishes connection to you, he/she will
> > send
> > > a NONCE(Dummy message) signed with his/her private key to prove his
> > > identity to you. When you receive the NONCE, you can try and decrypt
> > it
> > > using this partner's Public Key that you have already loaded into the
> > > queue, if it decrypts etc. etc. then it must be the partner because
> > only
> > > he/she has his/her private key.
> > > Now what troubles me here is that my colleague is not going ahead at
> > > this point and verifying this partner's key against the list of loaded
> > > CA Root certificates at the connection establishing time. What if I
> > > decide that I don't trust this particular Root CA anymore and thus I
> > > delete it from the certificate queue or what if the Root CA
> > certificate
> > > has been expired or even revoked. Since all my colleague's application
> > > is doing is verifying partner's certificate only at load time into the
> > > queue and never again. All certificates signed by this Root CA
> > > certificate will still authenticate a connection to me even if the
> > Root
> > > CA certificate has expired some time later or I have deleted it
> > because
> > > I don't trust it anymore or it has been revoked. I will physically
> > have
> > > to remove certificates from the cert queue of all clients/partners who
> > > had certificates issued by this CA to get them to not authenticate
> > with
> > > me.
> > > Does this seem like a standard implementation of public cryptographic
> > > algorithms to you? Is my concern warranted or not?
> > > Thanks in advance.
> > > Sincerely,
> > > Abid Farooqui
> >
> > Depends upon the period between refreshes of the CA queue. If it's
> > only a day or so, that's not bad. If it waits a year before changing
> > keys that can be bad.
> >
> > Typically you want to not change keys every three minutes, but the
> > ability to dynamically switch keys is a good idea.
> >
> > It really depends on the target as well. If you are using keys from a
> > sys-admin in an Intranet you don't want to switch the keys often since
> > you use them to verify requested public keys, etc.
> >
> > Maybe I misunderstood... just my 2c.
> >
> > Tom
> >
> > Sent via Deja.com http://www.deja.com/
> > Before you buy.
------------------------------
From: [EMAIL PROTECTED]
Subject: incremental prng?
Date: Sat, 13 May 2000 18:44:38 GMT
You know, last night I started pondering about stuff. You know how it
is, stuff gets intertwined with other stuff and you come up with
entirely new possibly irrelevant stuff.
I've once heard of random numbers being generated by using noise or
vibration or whatever the cpu makes. (Can't remember what it was, ..).
Let's say you use this and come up with a number, and then keep the less
significant digit. Nothing new here. Let's say you do this once every
second for 100 seconds and that becomes your seed (or what not..).
I don't have a math degree, but taking the least significant digit of N
at a determined time interval doesn't seem to random. I'm guessing you
could generate a pseudo random number with rand() [just an example) or
something and determine what random time interval to use between the
digit grabbing.. But you'd need a seed for that, too, and this is where
I'm getting at:
Suppose you generate a pseudo random number with whatever method is
currently in use, and then use that to time to first few intervals of
the digit grabbing from the cpu noise (or whatever, something not
software generated). Then, from the pseudo-random number you create with
the digit grabbing, (which will hereafter be called digits X), you use
digits X to generate a pseudo random number, but instead of using this
as your "final" random number, you use to figure out the next time
increment (in miliseconds, I suppose). If you keep using the results
from digits X to figure out new increments in the digit selecting, and
repeat this operation N number of times, then doesn't that make the
number "more random" than it would have been otherwise?
I know this is not very clear, I have little to no experience in
math/cryptography, but I was wondering if any of this made any sense to
anyone else.
Thanks for your time.
Sent via Deja.com http://www.deja.com/
Before you buy.
------------------------------
Subject: Re: Question regarding authentication implementation
Reply-To: Anne & Lynn Wheeler <[EMAIL PROTECTED]>
From: Anne & Lynn Wheeler <[EMAIL PROTECTED]>
Date: Sat, 13 May 2000 19:07:03 GMT
Abid Farooqui <[EMAIL PROTECTED]> writes:
> A colleague of mine has developed using BSAFE libraries a security
> application that does authentication at connection startup and
> encryption when data is transferred. The client certificates, Root
> certificates and client or partner certificates are stored in so called
> queue. When you load a client/partner certificate you can VERIFY that
> certificate against a list of available CA Root certificates that you
> already have in the queue. This is a completely separate step and is
> done in a non-active manner, meaning this happens way before the
> client/partner is establishing any kind of connection to you.
> Now, that you have a clinet/partner certificate loaded into a queue ...
> when the client/partner establishes connection to you, he/she will send
> a NONCE(Dummy message) signed with his/her private key to prove his
> identity to you. When you receive the NONCE, you can try and decrypt it
> using this partner's Public Key that you have already loaded into the
> queue, if it decrypts etc. etc. then it must be the partner because only
note that a certificate queue can be viewed as an account database ...
and the public key and the associated id information represents an
account record.
if this information is pre-loaded ... then there is no need to
transfer certificate(s) as part of each transaction.
a simple version of this was demonstrated at PC/EXPO a couple years
ago as "AADS" Radius ... i.e. Radius upgraded so that public key was
registered in the Radius id database ... and a signed transaction
(containing userid, time, & a couple other pieces) ... in place of
userid/password sequence.
the pre-loading can even be done w/o certificates of any kind ... in
the Radius case ... basically substitute the password registration
process with a public key registration process. it has the advantage
of eliminating shared-secret ... vis-a-vis existing userid/passwords.
misc. references:
http://www.garlic.com/~lynn/aadsm3.htm#kiss3
http://www.garlic.com/~lynn/2000b.html#14
http://www.garlic.com/~lynn/draft-wheeler-ipki-aads-01.txt
--
Anne & Lynn Wheeler | [EMAIL PROTECTED], [EMAIL PROTECTED]
http://www.garlic.com/~lynn/ http://www.adcomsys.net/lynn/
------------------------------
From: RaeNye <[EMAIL PROTECTED]>
Subject: Re: Theoretical question
Date: Sat, 13 May 2000 19:13:25 GMT
In article <[EMAIL PROTECTED]>, see.signature wrote:
{snip}
> > Could you please tell what's your definitaon of 'random functions'?
>
> A "random function" is usually taken to mean a function chosen
> uniformly at random from the set of all functions with a given
> domain and codomain. That's probably what the original poster meant.
{snip}
Exactly.
Rae
--
She sells C shells by the sea shore.
Sent via Deja.com http://www.deja.com/
Before you buy.
------------------------------
From: Wei Dai <[EMAIL PROTECTED]>
Subject: Re: Prime Generation in C,C++ or Java
Date: Sat, 13 May 2000 12:58:43 -0700
In article <8fic7i$c6d$[EMAIL PROTECTED]>, [EMAIL PROTECTED] says...
> I disagree. The exposed functions, even if implemented
> efficiently, are not useful in building efficient generators
> for primes of important special forms, for example DSA
> primes. To find DSA primes I want to simultaneously sieve
> for candidate pairs (q, p=d*q+1) where neither has a small
> factor, then do exactly one iteration of Miller-Rabin (with
> base 2) on q, then if that passes do the same on p, then if
> that passes do several randomized iterations to certify
> both. I have to write my own sieve and Miller-Rabin test
> because the class doesn't expose the ones it already has.
With DSA, is there any advantage to simultaneously sieving for p and q,
instead of the traditional method of generating q first and then
generating prime p of the form d*q+1? (Of course the traditional method
is not supported by the Java BigInteger interface either.)
What is your ideal interface for prime number generation? Would you care
to comment on the interface in Crypto++:
/// create a random integer of special type
/** Ideally, the random integer created should be uniformly distributed
over {x | min <= x <= max and x is of rnType and x % mod == equiv}.
However the actual distribution may not be uniform because sequential
search is used to find an appropriate number from a random starting
point.
May return (with very small probability) a pseudoprime when a prime
is requested and max > lastSmallPrime*lastSmallPrime (lastSmallPrime
is declared in nbtheory.h).
Throws RandomNumberNotFound if the set is empty.
*/
Integer(RandomNumberGenerator &rng, const Integer &min, const Integer
&max, RandomNumberType rnType=ANY, const Integer &equiv=Zero(), const
Integer &mod=One());
--
cryptopp.com - free C++ class library of cryptographic schemes
------------------------------
** 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 (and sci.crypt) via:
Internet: [EMAIL PROTECTED]
End of Cryptography-Digest Digest
******************************
