Cryptography-Digest Digest #326, Volume #14 Thu, 10 May 01 07:13:01 EDT
Contents:
Re: A simple encryption algorithm based on OTP (Bill Unruh)
Are low exponents a problem with RSA? (Matthew Kwan)
Re: A simple encryption algorithm based on OTP ("Siva Prasad Gummadi [T]")
Re: Probablistic Algorithms For Square Roots of QRs in Z/n (Tim Tyler)
Re: enumerating permutations (Tim Tyler)
Re: Integrity check algorithm ("Uros Podlogar")
Re: RSA BRUTE FORCE (Mark Wooding)
Re: Probablistic Algorithms For Square Roots of QRs in Z/n (Mark Wooding)
Re: Are low exponents a problem with RSA? (Mark Wooding)
Re: A simple encryption algorithm based on OTP ("Tom St Denis")
Re: Integrity check algorithm ("Tom St Denis")
Re: Random and not random (Bryan Olson)
Re: Random and not random (Vincent Quesnoit)
Re: Are low exponents a problem with RSA? (Bryan Olson)
Re: enumerating permutations ("Henrick Hellstr�m")
Re: A simple encryption algorithm based on OTP (" invisible inkie")
----------------------------------------------------------------------------
From: [EMAIL PROTECTED] (Bill Unruh)
Subject: Re: A simple encryption algorithm based on OTP
Date: 10 May 2001 06:59:58 GMT
In <[EMAIL PROTECTED]> "Siva Prasad Gummadi [T]" <[EMAIL PROTECTED]>
writes:
]
] Instead of using previous plain text for encrypting the plain
]text
]block, we'll use some variation of the key. The one which comes to mind
]is
]a permutation of the bits of key. If we have an algorithm to generate
Nope. That permutation must be known for the other side to use the same
one. Then one knows that say bit 8 of the permuted key is the same as
bit 5 of the original. Thus one can do the standard attack against a
reused OTP.
You are trying to generate what is called a stream cypher. There are
many (eg RC4), but they are slightly more complex than yours seems to
be.
------------------------------
From: [EMAIL PROTECTED] (Matthew Kwan)
Subject: Are low exponents a problem with RSA?
Date: 10 May 2001 17:59:47 +1000
Quick question about generating public/private keys for RSA.
Given the encryption function C = (P^e) mod n where (e,n) is
the public key, is there any security weakness in choosing a small
value of e?
mkwan
------------------------------
From: "Siva Prasad Gummadi [T]" <[EMAIL PROTECTED]>
Subject: Re: A simple encryption algorithm based on OTP
Date: Thu, 10 May 2001 14:01:43 +0530
Bill Unruh wrote:
> Nope. That permutation must be known for the other side to use the same
> one.
That's not at all a problem, if both of them agree upon a particular
permutation-generating program, obviously both get the same sequence of
permuted keys
> Then one knows that say bit 8 of the permuted key is the same as
> bit 5 of the original. Thus one can do the standard attack against a
> reused OTP.
I don't think it is similar ro 'reusing' a key. What extrainfo, he gets
if it is known that a particular bit is the same as in the original key?
For that matter, let's say that you've encrypted the text using OTP. I
can
break that long OTP keyt into blocks of keys, each of the length same
as my proposed key. Now, among these keys, obviously some bits do match
at a particular place, if you consider any two 'blocks' (keys). Do you
call it a case of reusing the key? Obviously not.
> You are trying to generate what is called a stream cypher. There are
> many (eg RC4), but they are slightly more complex than yours seems to
> be.
Please let me know if any one has found some specific method to crack
the proposed system. I am still bothered about the permutation
generating
program. I've written a small program, using cyclic permutations, but
it's
taking lot of time even for a 10-bit permutation.
Siva
--
************************************************************
Siva Prasad Gummadi
Motorola India Electronics Ltd.
No 33A, Ulsoor Road,
Bangalore - 560042
Phone No: 5598615-4007
email id: [EMAIL PROTECTED]
************************************************************
[x] General Information
[ ] Motorola Internal Use only
[ ] Motorola Confidential Proprietary
************************************************************
------------------------------
From: Tim Tyler <[EMAIL PROTECTED]>
Subject: Re: Probablistic Algorithms For Square Roots of QRs in Z/n
Reply-To: [EMAIL PROTECTED]
Date: Thu, 10 May 2001 08:51:41 GMT
Jeffrey Walton <[EMAIL PROTECTED]> wrote:
: Anyone have a heuristic or probabilistic Algorithm?
http://www.azillionmonkeys.com/qed/sqroot.html has some useful algorithms,
including some pretty rough-and-ready ones.
--
__________
|im |yler Try my latest game - it rockz - http://rockz.co.uk/
------------------------------
From: Tim Tyler <[EMAIL PROTECTED]>
Subject: Re: enumerating permutations
Reply-To: [EMAIL PROTECTED]
Date: Thu, 10 May 2001 08:59:06 GMT
Tom St Denis <[EMAIL PROTECTED]> wrote:
: I got bored in my College "Technical Math" class so I think I came up with a
: way to enumerate permutations [...]
The conventional way to number permutations is to put them into
lexicographic order. There's and existing algorithm to iteratively
generate permutations in this order.
The algorithm is described in: E. W. Dijkstra, A Discipline of
Programming, Prentice-Hall, 1976, p.71.
There's an implementation with source code in an applet on one of my pages:
http://mandala.co.uk/permutations/
--
__________ http://rockz.co.uk/ http://alife.co.uk/ http://hex.org.uk/
|im |yler http://atoms.org.uk/ http://mandala.co.uk/ [EMAIL PROTECTED]
------------------------------
From: "Uros Podlogar" <[EMAIL PROTECTED]>
Subject: Re: Integrity check algorithm
Date: Thu, 10 May 2001 11:19:06 +0200
I read about RSA and if I understand correct there is quite opposite. You
encode the message with public key, but you can decode this message only
with private key. I would like to encode message with private key and then
decode this message with public key. With this function everybody could
check message integrity, but no one could generate new message.
Regards
Uros
"Tom St Denis" <[EMAIL PROTECTED]> wrote in message
news:7ShK6.52980$[EMAIL PROTECTED]...
>
> "Uros Podlogar" <[EMAIL PROTECTED]> wrote in message
> news:zLhK6.8$[EMAIL PROTECTED]...
> > Here is short story. I would like to encode message with private key.
Then
> I
> > will publish message with public key. Everyone could decode message with
> > public key, but none could generate another message only with public
key.
> >
> > I would use this routine to sign the document so that everybody could
> check
> > its integrity, but nobody could change document and generate another
> > signature.
> >
> > Which algorithm should I use?
>
> Well you can use RSA or ElGamal to encode the hash of the message.
>
> Tom
>
>
------------------------------
From: [EMAIL PROTECTED] (Mark Wooding)
Subject: Re: RSA BRUTE FORCE
Date: 10 May 2001 09:47:14 GMT
Joseph Ashwood <[EMAIL PROTECTED]> wrote:
> That's been there for a while. I can't remember right now which
> algorithm it is (it was used a year ago in a demo in france on
> breaking an RSA key).
Fermat's method? Find an x such that x^2 - n = y^2 for some y, and then
factor n = (x + y)(x - y).
> I personally wouldn't even worry about it, don't bother changing
> your generation schemes.
Agreed.
-- [mdw]
------------------------------
From: [EMAIL PROTECTED] (Mark Wooding)
Subject: Re: Probablistic Algorithms For Square Roots of QRs in Z/n
Date: 10 May 2001 09:57:35 GMT
Jeffrey Walton <[EMAIL PROTECTED]> wrote:
> Anyone have a heuristic or probabilistic Algorithm?
>
> I was experimenting with Newton's method, but it acts like Pollard Rho in
> Zn.
If n is prime then you have no problem: there's a probabilistic
algorithm which gives you a square root mod a prime in expected
polynomial time.
If n is composite, you should factor n first. Extracting square roots
mod a composite n is as hard as factoring n. (Proof. Let n be
composite. Choose any x. Use your square-root algorithm to find y such
that y^2 = x^2 mod n. Then gcd(x - y, n) is a nontrivial factor of n
with probability at least 1/2.)
-- [mdw]
------------------------------
From: [EMAIL PROTECTED] (Mark Wooding)
Subject: Re: Are low exponents a problem with RSA?
Date: 10 May 2001 10:08:39 GMT
Matthew Kwan <[EMAIL PROTECTED]> wrote:
> Given the encryption function C = (P^e) mod n where (e,n) is
> the public key, is there any security weakness in choosing a small
> value of e?
Yes. You mustn't send more than e copies of a message (without padding)
to different people sharing the same value of e or the message will
leak. Similarly, sending e(e + 1)/2 linearly-related messages will leak
the messages. Finally, a neat attack by Coppersmith can recover a full
plaintext given sufficient partial information, if a low exponent was
used.
2^16 + 1 is almost certainly large enough. Use OAEP.
-- [mdw]
------------------------------
From: "Tom St Denis" <[EMAIL PROTECTED]>
Subject: Re: A simple encryption algorithm based on OTP
Date: Thu, 10 May 2001 10:16:49 GMT
"Siva Prasad Gummadi [T]" <[EMAIL PROTECTED]> wrote in message
news:[EMAIL PROTECTED]...
> My idea is to build a new, simple encryption algorithm based on OTP.
> While it's known that OTP is perfectly secure, it needs a key, which
> is of the same size as the plain text. But notice that actually we don't
> NEED such a perfect algo, but it'll suffice to have
> 1. A key that is difficult to crack by brute force
> 2. Involves simpler computations
> 3. The only way ot crack the algo. is brute force
>
> The previous algo. I've proposed is in fact defends against brute
> force.
> And as we know, the simplest possible computation is XOR. But the
> problem is
> that there are some methods other than by brute force (the one you've
> suggested
> is nice, and the known paintext block). I now try to propose some
> variations
> to the approach:
>
> Instead of using previous plain text for encrypting the plain
> text
> block, we'll use some variation of the key. The one which comes to mind
> is
> a permutation of the bits of key. If we have an algorithm to generate
> all
> possible permutations of the key (non repeated before the last possible
> one
> comes), I think that still makes the system secure, and I don't see any
> kinds of attacks possible other than brute force. Known plain text block
> kind of attack is not valid now. But the problem now, is with the
> permutation-generating program: do we have such an algo.? It should be
> smart and efficient.
Wow you're the first person to think of a "STREAM CIPHER". I suggest you
read some texts on crypto before declaring yourself the next Marlyn Vos
Savant...
Tom
------------------------------
From: "Tom St Denis" <[EMAIL PROTECTED]>
Subject: Re: Integrity check algorithm
Date: Thu, 10 May 2001 10:17:48 GMT
"Uros Podlogar" <[EMAIL PROTECTED]> wrote in message
news:9ddmd2$sie$[EMAIL PROTECTED]...
> I read about RSA and if I understand correct there is quite opposite. You
> encode the message with public key, but you can decode this message only
> with private key. I would like to encode message with private key and then
> decode this message with public key. With this function everybody could
> check message integrity, but no one could generate new message.
You have to read more. RSA can be used to sign messages.
Tom
------------------------------
From: Bryan Olson <[EMAIL PROTECTED]>
Subject: Re: Random and not random
Date: Thu, 10 May 2001 03:18:13 -0700
Mok-Kong Shen wrote:
>
> Bryan Olson wrote:
> >
> [snip]
> > Mok-Kong Shen wrote:
> > >
> > > Note that, if a dependency
> > > on the content of the OTP segments could result in
> > > any difference, that means directly I could determine
> > > one permutation out of the 6 that the opponent has the
> > > least chance of success and consequently I should have
> > > chosen that one, instead of making a random choice (your
> > > independent choice). Is that right?
> >
> > It is wrong. We assume the method, but not the key, is
> > known to the attacker. See Shannon's paper or the FAQ.
>
> I think I could even rigorously prove my claim. Let's
> denote the original and perfect strategy of choosing the
> permutation with U, where, in order to ensure absolute
> no dependency on the content of the OTP segements, I
> additionally employ a perfect die to determine the
> permutation to be used, thus avoiding any conceivable
> human bias. Are you entirely satisfied?
That's more complex than it needs to be, but yes it's fine.
> Under U, the
> opponent's chance of cracking the messages is thus zero.
> Right?
Of course not. In this very thread you cited "Shannon's
classical papers" as good sources. Perfect secrecy means
the conditional probability of each message given the
ciphertext is the same as the /a priori/ probability of that
message when not given the ciphertext. Where did you get
this zero probability?
> Now I devise a second strategy V in that I
> carefully examine the pad and from that information
> determine (according to a certain algorithm designed by
> me) which permutation to choose. According to what you
> have hithertofore maintained up till now, the perfect
> security of OTP is thereby gone, for now the choice
> depends (in fact strongly depends) on the content of
> the OTP segements. Right? That is, the opponent now
> has a certain non-zero probability P to crack the
> messages.
It means the ciphertext can carry some information about
the plaintext.
> Note however that under U one of the 6
> alternatives is randomly chosen, while under V a
> particular one of the 6 is (deterministically) chosen
> (from the same set of alternatives). Thus there is
> a non-zero probability Q that the selection of U and the
> selection of V coincide. (Offhand I think that Q=1/6,
> but the exact value doesn't matter.) Therefore,
> according to the above, the opponent should have under
> U a non-zero probability of P*Q of cracking the messages,
> which is contradictory to the original assumption that
> U provides the perfect security of OTP.
Clearly incorrect. Attacking the two systems is not the
same problem. In the second case the attacker has the
information that the key induced the chosen permutation.
Using the key in that way results in non-uniform
probabilities and the attacker can compute the deviation
from uniform. This extra information allows him to reduce
the equivocation of the plaintext when given the ciphertext.
On the plus side, the argument was stated precisely enough
to allow specific determination of where it goes wrong.
--Bryan
------------------------------
From: Vincent Quesnoit
Subject: Re: Random and not random
Date: Thu, 10 May 2001 11:54:02 +0200
Reply-To: [EMAIL PROTECTED]
Mok-Kong Shen a �crit :
>
> I think I could even rigorously prove my claim. Let's
> denote the original and perfect strategy of choosing the
> permutation with U, where, in order to ensure absolute
> no dependency on the content of the OTP segements, I
> additionally employ a perfect die to determine the
> permutation to be used, thus avoiding any conceivable
> human bias. Are you entirely satisfied? Under U, the
> opponent's chance of cracking the messages is thus zero.
> Right? Now I devise a second strategy V in that I
> carefully examine the pad and from that information
> determine (according to a certain algorithm designed by
> me) which permutation to choose. According to what you
> have hithertofore maintained up till now, the perfect
> security of OTP is thereby gone, for now the choice
> depends (in fact strongly depends) on the content of
> the OTP segements. Right? That is, the opponent now
> has a certain non-zero probability P to crack the
> messages. Note however that under U one of the 6
> alternatives is randomly chosen, while under V a
> particular one of the 6 is (deterministically) chosen
> (from the same set of alternatives). Thus there is
> a non-zero probability Q that the selection of U and the
> selection of V coincide. (Offhand I think that Q=1/6,
> but the exact value doesn't matter.) Therefore,
> according to the above, the opponent should have under
> U a non-zero probability of P*Q of cracking the messages,
> which is contradictory to the original assumption that
> U provides the perfect security of OTP.
>
> M. K. Shen
> --------------------------------
> http://home.t-online.de/home/mok-kong.shen
You are talking about an isolated message here, or you make the
assumption that the opponent knows nothing about yourself.
Your arguments do not work as soon as the oponent sees several messages
that where subjected to your choice. In that case the way you pick the
pads will show when one compares the various messages you sent
Even when one sees only one message, after reading this thread, the
opponent would know that you prefer not to use an OTP that contains long
strings of ones or long strings of zeroes, so the opponent would be able
to eliminate a number of possible source messages, on the basis that
your selection of OTP has such a feature.
V.Quesnoit
------------------------------
From: Bryan Olson <[EMAIL PROTECTED]>
Subject: Re: Are low exponents a problem with RSA?
Date: Thu, 10 May 2001 03:27:21 -0700
Matthew Kwan wrote:
>
> Quick question about generating public/private keys for RSA.
>
> Given the encryption function C = (P^e) mod n where (e,n) is
> the public key, is there any security weakness in choosing a small
> value of e?
As long as you use proper message padding (see PKCS #1) there
is no known problem with small public RSA exponents such as 3.
Some experts suspect small public exponents are likely to be
weaker than random exponents, and other experts disagree.
--Bryan
------------------------------
From: "Henrick Hellstr�m" <[EMAIL PROTECTED]>
Subject: Re: enumerating permutations
Date: Thu, 10 May 2001 12:34:58 +0200
"Tim Tyler" <[EMAIL PROTECTED]> skrev i meddelandet
news:[EMAIL PROTECTED]...
> Tom St Denis <[EMAIL PROTECTED]> wrote:
>
> : I got bored in my College "Technical Math" class so I think I came up
with a
> : way to enumerate permutations [...]
>
> The conventional way to number permutations is to put them into
> lexicographic order. There's and existing algorithm to iteratively
> generate permutations in this order.
>
> The algorithm is described in: E. W. Dijkstra, A Discipline of
> Programming, Prentice-Hall, 1976, p.71.
>
> There's an implementation with source code in an applet on one of my
pages:
>
> http://mandala.co.uk/permutations/
Have you tried that with permutations of length = 256? Don't. ;-)
--
Henrick Hellstr�m [EMAIL PROTECTED]
StreamSec HB http://www.streamsec.com
------------------------------
From: " invisible inkie" <[EMAIL PROTECTED]>
Subject: Re: A simple encryption algorithm based on OTP
Date: Thu, 10 May 2001 13:04:11 +0200
<delurk>
"Tom St Denis" dropped into the real world with a crash and proclaimed...
>
> "Siva Prasad Gummadi [T]" <[EMAIL PROTECTED]> wrote in message
<snip>
>
> Wow you're the first person to think of a "STREAM CIPHER". I suggest you
> read some texts on crypto before declaring yourself the next Marlyn Vos
> Savant...
And I suggest you read some texts on social skills before dealing with
people again!
I respect your knowledge a lot, Tom, and I'm the first to admit that
I eagerly read your posts, because I learn a lot from them, but every
now and then I blow my top at your way of posting!
Siva was proposing something, and compared to other people who
are new here, he described it pretty seriously. He said "I think"
where others would've written "I know" without doing so. He didn't
declare himself anything, he didn't claim he'd found a golden rule,
he just asked for feedback, and he did it politely, ferchrissake!
Easy on the lemming, Tom, not everyone is (yet) as knowledgeable
as you are! Give them some time and, what I as a teacher think even
more important, patience and respect. Their points might be as valid
as yours.
Cheers,
ink
</delurk>
------------------------------
** 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
******************************
