Cryptography-Digest Digest #436, Volume #13 Sun, 7 Jan 01 13:13:01 EST
Contents:
Re: Differential Analysis (Simon Johnson)
Re: Differential Analysis (Tom St Denis)
Re: Fastest way to factor primes? (Simon Johnson)
Re: Fastest way to factor primes? (Bob Silverman)
Re: Question regarding OS's. ([EMAIL PROTECTED])
Re: Need of very simple algorithms? ("Brian Gladman")
Re: Fastest way to factor primes? (Quisquater)
Re: Fastest way to factor primes? (Steve Portly)
Re: Fastest way to factor primes? (Tom St Denis)
Re: xor'd text file ("Joshua Cryer")
Re: Need of very simple algorithms? (SMS end-to-end encryption) (Mok-Kong Shen)
Re: Need of very simple algorithms? (Mok-Kong Shen)
Re: Need of very simple algorithms? ("r.e.s.")
----------------------------------------------------------------------------
From: Simon Johnson <[EMAIL PROTECTED]>
Subject: Re: Differential Analysis
Date: Sun, 07 Jan 2001 13:23:50 GMT
In article <9381mn$6us$[EMAIL PROTECTED]>,
Tom St Denis <[EMAIL PROTECTED]> wrote:
> In article <937nrs$vhb$[EMAIL PROTECTED]>,
> Simon Johnson <[EMAIL PROTECTED]> wrote:
> > The bit i never get with this. Is that we find say the highest prob
> > output difference, then what?
>
> Then you exploit it.
>
> If you know the input pairs that exhibit the difference (in the
output)
> then by sending random pairs (that differ by the correct amount) and
> exhibit the output difference you can guess what the key may have
been.
>
> Simple example:
>
> Let's say the input difference of '1' makes an output difference
of '1'
> with a prob of 4/256. That means there are two pairs that exibit the
> difference. Let's say (0, 1) and (2,3) are our pairs. Then if I send
> (4,5) into the function and get (7,8) as the two outputs (i.e you have
> vectors of the form vec A = <4, F(4)> and vec B = <5, F(5)> and the
> difference between the two vectors is B-A = <1, 1>) then we can guess
> the key may have been 4 or 2.
>
> This is all using addition in Z not in GF(2) of course.
>
> Tom
>
> Sent via Deja.com
> http://www.deja.com/
>
For x rounds would u need roughly (4/256)^x known plain-texts to solve
for this example.... or is the relationship more complex?
--
Hi, i'm the signuture virus,
help me spread by copying me into Signiture File
Sent via Deja.com
http://www.deja.com/
------------------------------
From: Tom St Denis <[EMAIL PROTECTED]>
Subject: Re: Differential Analysis
Date: Sun, 07 Jan 2001 13:50:26 GMT
In article <939ql3$fop$[EMAIL PROTECTED]>,
Simon Johnson <[EMAIL PROTECTED]> wrote:
> In article <9381mn$6us$[EMAIL PROTECTED]>,
> Tom St Denis <[EMAIL PROTECTED]> wrote:
> > In article <937nrs$vhb$[EMAIL PROTECTED]>,
> > Simon Johnson <[EMAIL PROTECTED]> wrote:
> > > The bit i never get with this. Is that we find say the highest
prob
> > > output difference, then what?
> >
> > Then you exploit it.
> >
> > If you know the input pairs that exhibit the difference (in the
> output)
> > then by sending random pairs (that differ by the correct amount) and
> > exhibit the output difference you can guess what the key may have
> been.
> >
> > Simple example:
> >
> > Let's say the input difference of '1' makes an output difference
> of '1'
> > with a prob of 4/256. That means there are two pairs that exibit
the
> > difference. Let's say (0, 1) and (2,3) are our pairs. Then if I
send
> > (4,5) into the function and get (7,8) as the two outputs (i.e you
have
> > vectors of the form vec A = <4, F(4)> and vec B = <5, F(5)> and the
> > difference between the two vectors is B-A = <1, 1>) then we can
guess
> > the key may have been 4 or 2.
> >
> > This is all using addition in Z not in GF(2) of course.
> >
> > Tom
> >
> > Sent via Deja.com
> > http://www.deja.com/
> >
> For x rounds would u need roughly (4/256)^x known plain-texts to solve
> for this example.... or is the relationship more complex?
The rule is you generally need 2/p plaintexts to exhibit the
characteristic. And yes it *can* chain like (2/p)^x for 'x' rounds.
This chain rule doesn't always hold. And sometimes you can exbihit the
char. in more/less then the 2/p bound.
Tom
Sent via Deja.com
http://www.deja.com/
------------------------------
From: Simon Johnson <[EMAIL PROTECTED]>
Subject: Re: Fastest way to factor primes?
Date: Sun, 07 Jan 2001 13:50:47 GMT
In article <[EMAIL PROTECTED]>,
Steve Portly <[EMAIL PROTECTED]> wrote:
> What would be the fastest way to determine if 362,293,147 is prime?
> Wouldn't a prime number sieve be the fastest method?
>
>
Just about the way you named this thread. To test wether a number is
prime you do not factor. Asking the question 'What are the factors of N'
is different to asking 'Is N prime'. The complexity of factoring is
believed to increase expodentially with an increase in input size. The
complexity of determining wether 'N' is prime increase to the form of a
polynomial with increase in input size. Clearly, the later problem is
simpler to solve.
As for checking wether 362,293,147 is prime.... A prime number sieve
would work. But simple brute force is simpler to code for such a small
number. For enormas numbers probalistic methods are better.
It actually isn't prime, 19031 and 19037 are its two factors.
Simon.
--
Hi, i'm the signuture virus,
help me spread by copying me into Signiture File
Sent via Deja.com
http://www.deja.com/
------------------------------
From: Bob Silverman <[EMAIL PROTECTED]>
Subject: Re: Fastest way to factor primes?
Date: Sun, 07 Jan 2001 14:40:18 GMT
In article <[EMAIL PROTECTED]>,
Steve Portly <[EMAIL PROTECTED]> wrote:
> What would be the fastest way to determine if 362293147 is prime?
> Wouldn't a prime number sieve be the fastest method?
When someone asks for "the fastest method", it is usually
an indication that they have not thought about the problem.
THE FASTEST METHOD is table lookup. It can be done in time
proportional to log(p). Of course, it requires a very large
table, but your question did not prohibit this.....
When one asks for "fastest method", one must be very careful
to state any constraints on the allowed resources...
--
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/
------------------------------
From: [EMAIL PROTECTED]
Subject: Re: Question regarding OS's.
Date: Sun, 07 Jan 2001 15:06:01 GMT
[EMAIL PROTECTED] wrote:
> I have a windows 95 box that I spend the most time on, and have been
> attempting to use the DOS | command to use the output of my program to
> serve as input for another program, to no avail. Is the usage of data
> piping (such as you described in the UNIX shell environment), how
> cryptoanalysis programs are actually implemented? Thank you very
> much! Ed
You should also be aware that because the DOS interpreter dates back
to the PC's single-taskign days pipes are implemented using temporary
files, not pipes. (At least until dos 5, but I don't believe
command.com has been seriously revised since) That means the previous
command in the pipeline must terminate before the next is even
started. It's also why 'type file.txt | more' is much slower than
'more < file.txt' for large files.
In the first case, file.txt is copied to a temporary directory, and
then the second command is executed. On a unix system, both the
commands would be executed simultaneously. If you really want pipes in
win95, you'll probably have much better luck installing cygwin and
using the bash port rather than command.com.
--
Matt Gauthier <[EMAIL PROTECTED]>
------------------------------
From: "Brian Gladman" <[EMAIL PROTECTED]>
Subject: Re: Need of very simple algorithms?
Date: Sun, 7 Jan 2001 15:23:50 -0000
"Mok-Kong Shen" <[EMAIL PROTECTED]> wrote in message
news:[EMAIL PROTECTED]...
>
>
> Paul Pires wrote:
> >
>
> > I have also seen a bunch of cheeper and much more capable
> > electronic toys. I was wondering why you feel a need to limit
> > the possible solutions to a mechanical apparatus.
>
> Any practical scheme that is suitable and sufficiently
> good for the situation in question would be fine. See below.
>
> > My apologies if my comments are off track but...
> > What are "SMS messages"? You can probably
> > guess that I don't have anything usefull and on
> > topic but I don't understand the target need
> > as you discribe it.
>
> I meant those text messages that are sent by handy users.
> (Sorry, if the acronym I used is not universally accepted.)
> A normal handy user doesn't carry any computing device
> with him for running sophisticated encryption algorithms.
> That's the problem.
What does your 'handy user' have to do encryption with? If he or she has
anything more than their brain it may well be good enough to run AES.
AES is simple enough to implement in mobile phones, in hand held devices
like the Palm Pilot (where it is already available) and in a number of
scientific calculators (e.g. TI86).
Brian Gladman
------------------------------
From: Quisquater <[EMAIL PROTECTED]>
Subject: Re: Fastest way to factor primes?
Date: Sun, 07 Jan 2001 17:32:18 +0100
Bob Silverman wrote:
>
> In article <[EMAIL PROTECTED]>,
> Steve Portly <[EMAIL PROTECTED]> wrote:
> > What would be the fastest way to determine if 362293147 is prime?
> > Wouldn't a prime number sieve be the fastest method?
>
> When someone asks for "the fastest method", it is usually
> an indication that they have not thought about the problem.
>
> THE FASTEST METHOD is table lookup. It can be done in time
> proportional to log(p). Of course, it requires a very large
> table, but your question did not prohibit this.....
[Reader, be careful about the subject of this news]
Dear Bob,
Think again about the model! Quantum computation? Associative memories?
Here is a solution in O(log(log(p))
If there is no restriction (speed of light is "infinite" and there is no
restriction about the space -- same remark holds for your method of table
lookup: think how to implement it in a 3D space ...) you broadcast the
question (the number to be prime or not) using a distinct length of wave for
each bit of the number. Each element of the distributed network
has a number (= a possible question) and contains a result (one bit with
the result if this number is prime or not) and is able to do the following:
- receiving the question in O(1) time:
- deciding if the received number is relevant (its own number) in O(log(log(p)):
- if no, do nothing:
- if yes, will send the result.
Indeed, the element receives a number with log(p) bits and a decision tree
needs log(log(p) comparisons:
- sending the result (one bit) in O(1) time by broadcasting.
The model thus is very important.
Jean-Jacques,
------------------------------
From: Steve Portly <[EMAIL PROTECTED]>
Subject: Re: Fastest way to factor primes?
Date: Sun, 07 Jan 2001 12:13:31 -0500
Brian Wong wrote:
> "Virgil" <[EMAIL PROTECTED]> wrote in message
> news:[EMAIL PROTECTED]...
> > In article <[EMAIL PROTECTED]>, Steve Portly
> > <[EMAIL PROTECTED]> wrote:
> >
> > > What would be the fastest way to determine if 362293147 is prime?
> > > Wouldn't a prime number sieve be the fastest method?
> > >
> >
> > To find a lot of primes fast, a sieve is probably the most efficient
> > way, but the size of the primes is limited.
> >
> > To find whether a single number is prime, there are better ways.
> >
> > My HP49G hand calculator factored 362293147 into 19031*19037 in about a
> > second and a half.
>
> Simply run a SPRP to bases 2, 3, 5, and 7. If the number is not
> 3,215,031,751 and is under 100,000,000,000 it is prime.
> Alternately, run a SPRP to base 2 and a Lucas test. No counterexamples are
> known (although they must exist, you aren't too likely to find one).
>
> Brian
So the fastest method for factoring a prime depends on the size of the prime.
For very large primes would the Shor quantum algorithm always be the fastest?
http://www.dwavesys.com/Demos/demo.html
------------------------------
From: Tom St Denis <[EMAIL PROTECTED]>
Subject: Re: Fastest way to factor primes?
Date: Sun, 07 Jan 2001 17:08:27 GMT
In article <[EMAIL PROTECTED]>,
Steve Portly <[EMAIL PROTECTED]> wrote:
> What would be the fastest way to determine if 362293147 is prime?
> Wouldn't a prime number sieve be the fastest method?
Just to quip about the subject, you can't factor prime numbers, they
are by nature irreducible.
I think you meant to ask "Fastest way to factor a composite into
primes?".
Tom
Sent via Deja.com
http://www.deja.com/
------------------------------
From: "Joshua Cryer" <[EMAIL PROTECTED]>
Subject: Re: xor'd text file
Date: Sun, 7 Jan 2001 09:25:52 -0800
> It is my humble opinion that the task may not be easy. But
> the general opinion seems to be that anything using PRNG
> is very easy to crack. On the other hand, the experts who
> are prompt to claim this seldom show 'concrete' examples
> to do that. Perhaps this thread could lead to some practical
> knowledge for the less initiated.
>
> M. K. Shen
I agree that the task would be very difficult indeed. I would think that to
crack anything XOR'd to a PRNG you would need to know two things. One, how
the PRNG works. (That is, having actual access to the PRNG, and being able
to test it.) Two, a lot of time. A whole crapload of time. Whenever you XOR
a file to PRNG, you have to repeat the exact steps backwards. If you used
the seeds 1 2 and 3 consecutively, you would have to repeat them backwards
as: 3 2 and 1 to decrypt. I know I'm probably pointing out the obvious to
you guys. I just want make people realize that there are:
(S^S)^N combonations. Where N is the number of iterations, and S is the size
of PRNG.
So for a 16 bit PRNG you would be looking at an incredible length of
cracking time. This is of course having access to the PRNG encryptor. If you
don't have access to the encryptor? Well, you're crap out of luck. :-)
I'm assuming all of this though, because I don't know anything about
encryption at all. Perhaps there is an wasy way to find patterns in this
type of file, that's the whole reason I started this thread. If that's the
case, someone, please reply.
If someone doesn't answer this question with some reasonably clear methods
to find patterns created by PRNG XOR encryptors, I will be compelled to
write a simple C program that would XOR using the Mersenne Twister PRNG, and
propose that someone crack a file created by it. Frankly, without the
encryptor I don't think it would be easily feasible. And even with it, you
would be looking at a very long cracking time. :-P
By the way, please forgive my arrogance, as I have honestly tried to figure
out how to reverse engineer a file for quite some time now. And my IQ leads
me to believe what I have said here is true.
------------------------------
From: Mok-Kong Shen <[EMAIL PROTECTED]>
Subject: Re: Need of very simple algorithms? (SMS end-to-end encryption)
Date: Sun, 07 Jan 2001 18:29:43 +0100
Marc wrote:
>
> >Plenty of people are nowadays sending SMS messages to one
> >another, often en route. What can one do to obtain some degree
> >of security for such messages (assuming that nothing of the
> >genre of a palmtop is available)?
>
> Isn't this rather a task for the mobile phone? They come
> with 16-32bit MCU+DSP, 1-4MB of Flash memory, 64-256KB of
> SRAM and typically run at 13 MHz. There are enough resources
> available to implement an end-to-end SMS encryption. For
> some mobiles, flasher tools exist on the web, so you can
> start to develop without waiting for new ETSI recommendations :-)
>
> Another approach is the SIM card, most mobiles first store
> incoming messages on the SIM, and later read them back for
> display. A homebrew "custom" SIM could magically handle
> the decryption at this stage. This would be a more easy
> to develop solution, and not bound to a single phone brand.
> Public skeleton SIM implementations exist on the web, and
> example programs to extract the key from COMP128 SIMs, too
> (to copy the existing subscription to the homebrew SIM).
> Nothing is missing really, except for a few weekends of
> work.
>
> A variation of the latter is a man-in-the-middle chip that
> intercepts the comm between mobile and SIM. It is very
> easy to "add" new files to the SIM or "change" existing
> files' contents with this approach, while leaving all
> the other functionality of the SIM intact (eg provider
> specific SIM Application Toolkit). Disadvantage is the
> necessary hardware modification and the shorter standby
> time (extra chip), but compatibility and portability
> is a maximum. I made some code in the past that handles
> the comm all right and works with any SIM.
Your viewpoint is essentially correct and the new handys
that has WAP capability and supposed to be used in
M-commerce are to have crypto features built in, I conjecture.
However, there are currently a huge number of handy users
who just possess a simple handy and don't have the knowledge
(or don't want to take the trouble) to do the modification
you described. That's why I suppose that there could be a
utility of some simple devices like the Jefferson cylinder.
I think also that there even could be a business niche to
manufacture portable encryption devices based on AES
of the size of a tiny calculator. Since the messages to be
handled are short (this applies even for some of e-mails),
one can use cheap (slow-running) hardware, particularly
if there is a correspondingly large volume of sells
to lower the price of the product. (One advantage of such
separate devices would be that it can also be used with a
PC without the risk of the PC being bugged.)
M. K. Shen
------------------------------
From: Mok-Kong Shen <[EMAIL PROTECTED]>
Subject: Re: Need of very simple algorithms?
Date: Sun, 07 Jan 2001 18:29:49 +0100
Brian Gladman wrote:
>
> What does your 'handy user' have to do encryption with? If he or she has
> anything more than their brain it may well be good enough to run AES.
>
> AES is simple enough to implement in mobile phones, in hand held devices
> like the Palm Pilot (where it is already available) and in a number of
> scientific calculators (e.g. TI86).
The problem is that currently we don't yet have handys
(at the market) that have AES built-in and there are
already a huge number of handys without that in possession
of people. As to palmtop, I have excluded it as assumption
in my original post. with certain tarifs one gets a handy
for free from the provider. A palmtop is expensive, at least
for a large class of handy users of the world. A simple-minded
mechanical device could cost almost nothing, though certainly
by far not offering the high security of AES, which are
likely not to be needed for the application in question.
M. K. Shen
------------------------------
From: "r.e.s." <[EMAIL PROTECTED]>
Subject: Re: Need of very simple algorithms?
Date: Sun, 7 Jan 2001 09:57:34 -0800
"Mok-Kong Shen" <[EMAIL PROTECTED]> wrote ...
| Paul Pires wrote:
[...]
| > What are "SMS messages"?
[...]
|
| I meant those text messages that are sent by handy users.
| (Sorry, if the acronym I used is not universally accepted.)
| A normal handy user doesn't carry any computing device
| with him for running sophisticated encryption algorithms.
A "handy" is a kind of mobile phone?
SMS mean "Short Message Service" for
messages of 1120 bits max?
--r.e.s.
------------------------------
** 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
******************************
