Cryptography-Digest Digest #122, Volume #14 Tue, 10 Apr 01 23:13:01 EDT
Contents:
Re: Steganography with natural texts (Mok-Kong Shen)
Re: Delta patching of encrypted data ("Anon")
Re: Steganography with natural texts (Mok-Kong Shen)
Re: Dynamic Substitution Question (Mok-Kong Shen)
Re: Dynamic Substitution Question (newbie)
Re: NESSIE reports (Mok-Kong Shen)
Re: Current best complexity for factoring? (Jerry Coffin)
Re: Delta patching of encrypted data (David Wagner)
Re: Current best complexity for factoring? (Steve Portly)
Re: Frobenius map over q-adic integers (David Moews)
Re: AES Inverse trick (Mark Wooding)
Re: Current best complexity for factoring? ("Scott Fluhrer")
Re: Dickson Polynomials? ("Simon Johnson")
Re: MIPS Ratings for Encryption Algorithms ("Simon Johnson")
----------------------------------------------------------------------------
From: Mok-Kong Shen <[EMAIL PROTECTED]>
Subject: Re: Steganography with natural texts
Date: Wed, 11 Apr 2001 00:25:35 +0200
Joe H Acker wrote:
>
[snip]
> That's the rough sketch of my ideas. If it sounds like bullshit, please
> anyone feel free to tell me about it, but please also take some time to
> explain to me why.
I must admit that I have yet some difficulty to fully
capture your post. But instead of asking questions on
a number of detailed points of the text of yours, I
would like to ask whether the following could be conform
to what you said:
The material that is normally transmitted has certain
"observable statistical properties" (which presumably
means all statistical properties that can be assumed
to be discernable by the opponent). The modified
stuff, in which the message bits are concealed, should
have 'exactly' the same properties.
Assuming that the answer is Yes, I think that there
are a couple of (practical) issues that need be tackled:
(1) As you said, the definition of "observable statistical
properties" is crucial. Statistics is a very well
developed branch of mathmatics but crypto concerns it
only marginally. Are the statistical properties
commonly discussed in textbooks (and apparently
applicable to bit sequences) all that we need or
do we have to dig deeper into the ensemble of
literatures of statistics and probability, which
is huge? Are we sure that we haven't missed something
that belongs to the opponent's (larger) set of the
said properties?
(2) Is it at least possible in theory to obtain 'exactly'
the same "observable statistical properties"? Any
rigorous proof? If not (or if yes but in practice
not), what is the maximal measure of deviations that
can be tolerated for having a 'secure' system?
(3) Presumably we need to examine the statistical
properties not only in 1-bit units but also in n-bit
units. What is the range of n that we need to
consider? (We certainly couldn't have an arbitrarily
large range for reasons of practical computation.)
I am a bit pessimistic on availability of satisfactory
answers to these.
M. K. Shen
------------------------------
From: "Anon" <[EMAIL PROTECTED]>
Subject: Re: Delta patching of encrypted data
Date: Tue, 10 Apr 2001 23:31:13 -0000
David,
as I suspected we are at cross purposes.
When my program encrypts the original file, I can chop it up into chunks.
These can be any size I like - 4096 bytes, the Insel Intide hardware page is
as good as any. I ship this file.
Then I'm given another file at a later date. I don't have the original file
available at this time. (this is the problem!)
When I get to the chunk with the insertion (or deletion) I need to input
information about the old encrypted file in order to find what chunks I used
last time. But I don't have that information!
I can see where you are heading now. It is certainly something I will bear
in mind - if it is possible at some later date to change our system so that
we keep the old encrypted files available, or at least information about
them, I'd end up with a system that decrypts far faster than anything I've
come up with.
Thanks for the input!
"David Wagner" <[EMAIL PROTECTED]> wrote in message
news:9atojr$9d3$[EMAIL PROTECTED]...
> Let me try again. AES has a 16-byte block size. Let's take a maximum
> chunk size of 256 blocks (= 4096 bytes). A chunk is represented as a
> length byte M followed by an IV (16 bytes) followed by exactly M blocks
> (16*M bytes) of ciphertext. The ciphertext is obtained by encrypting
> the plaintext with padded-AES-CBC mode using the provided IV. A file
> is a sequence of chunks.
>
> Now suppose you want to insert a byte into a chunk. If the chunk
> has length M < 256, then you can just decrypt, insert the byte, and
> re-encrypt. If the chunk has length M = 256, decrypt and split it into
> two halves, then insert the byte into the appropriate half, then encrypt
> each half into a new chunk. (Each new chunk will have about 128 blocks
> in it.) Deletion is even easier: if the chunk length is M > 1, then you
> decrypt the chunk, delete the byte, and re-encrypt; if the chunk length
> is M = 1, you delete the whole chunk. Thus, each insertion or deletion
> involves modifying at most 256 blocks (4096 bytes) of the file.
>
> This is one approach. It may not be the optimal one, but it might be
> good enough for your purposes.
------------------------------
From: Mok-Kong Shen <[EMAIL PROTECTED]>
Subject: Re: Steganography with natural texts
Date: Wed, 11 Apr 2001 00:58:10 +0200
John Bailey wrote:
>
> Combining thoughts inspired by your post with another current thread.
> The other thread is the one which offered the challenge of dual
> decryption, such that a key can be provided to authorities who demand
> it without disclosing the real content of the message..
>
> Use a simplistic subsitution encryption scheme a la the Captain
> Midnight decoder ring in which each character in plaintext is paired
> with one cyphertext character, but with the following modification.
> Once the same substitution has been made twice, the
> plaintext/cyphertext pairing list is advanced by 1. Because this
> scheme reduces the opportunity to use letter frequency as a clue, this
> offers a way to use simple substitution without the resulting
> cryptoanalysis becoming quite as simple as solving a new york times
> cryptogram. Such a scheme might be useful for hand encrypting. Now
> for the stegano.
>
> As each usage threshold is reached, the selection of the next
> substitution symbol could be from multiple choices. In the simplest
> case, suppose there are only two choices provided, the selection
> embeds one bit. So, we have a means of hiding in superficially
> encrypted material, one bit per every two characters of a
> steganoverlay (on average)
>
> This scheme also provides an answer to encryption where a totalitarian
> authority can demand a key for decrytion. Only the choices used need
> be disclosed.
Sorry, I failed to identify 'the other thread' and am
ignorant of the method of the decoder ring. So my
interpretation of your text could be erroneous.
As far as I understood, the sequence sent is not a normal
English text, which would mean that anybody knows that
there is some secret in it and the scheme thus wouldn't
qualify as stego (but as a method to circumvent some
crypto laws), I am afraid.
M. K. Shen
------------------------------
From: Mok-Kong Shen <[EMAIL PROTECTED]>
Subject: Re: Dynamic Substitution Question
Date: Wed, 11 Apr 2001 01:16:57 +0200
newbie wrote:
>
> It is not a good solution Dynamic Substitution as presented by Ritter.
> It contains a very big hole.
> You have just to analyze it carefully.
> Using the combiner DS, reveal the sequence of the keystream.
> Just try to analyze it before talking about claiming.
> Claiming of what?
> Something completely wrong.
I wouldn't have written this follow-up, if you hadn't
attach my previous post to it. Sorry for expressing my
direct viewpoints below.
We have been discussing in this thread the exact coverage
of the patent and (when that is clearly delineated) the
novelty/utility of the feactures in it. I don't see what
you wrote above concerns that issue in the proper sense.
Using very general and vague claims ('big hole',
'completely wrong') without providing concrete and clearly
understandable supporting materials is not a desirable
manner of conducting scientific discussions in my humble
opinion.
M. K. Shen
------------------------------
From: newbie <[EMAIL PROTECTED]>
Subject: Re: Dynamic Substitution Question
Date: Tue, 10 Apr 2001 19:24:38 -0300
Did you studied it?
You have just to try to implement DS, to compute it and to see the real
results.
Not what Ritter is claiming.
You will find that OTP even if used with bad PRNG is better.
Test it.
Mok-Kong Shen wrote:
>
> newbie wrote:
> >
> > It is not a good solution Dynamic Substitution as presented by Ritter.
> > It contains a very big hole.
> > You have just to analyze it carefully.
> > Using the combiner DS, reveal the sequence of the keystream.
> > Just try to analyze it before talking about claiming.
> > Claiming of what?
> > Something completely wrong.
>
> I wouldn't have written this follow-up, if you hadn't
> attach my previous post to it. Sorry for expressing my
> direct viewpoints below.
>
> We have been discussing in this thread the exact coverage
> of the patent and (when that is clearly delineated) the
> novelty/utility of the feactures in it. I don't see what
> you wrote above concerns that issue in the proper sense.
> Using very general and vague claims ('big hole',
> 'completely wrong') without providing concrete and clearly
> understandable supporting materials is not a desirable
> manner of conducting scientific discussions in my humble
> opinion.
>
> M. K. Shen
------------------------------
From: Mok-Kong Shen <[EMAIL PROTECTED]>
Subject: Re: NESSIE reports
Date: Wed, 11 Apr 2001 01:26:57 +0200
Jakob Jonsson wrote:
>
> Public reports of the NESSIE project:
>
> https://www.cosic.esat.kuleuven.ac.be/nessie/reports/
I tried to access the article 'LILI-128 stream cipher'
in it, but I got a completely blank page. Does anyone
succeed to get that?
M. K. Shen
------------------------------
From: Jerry Coffin <[EMAIL PROTECTED]>
Subject: Re: Current best complexity for factoring?
Date: Tue, 10 Apr 2001 17:57:41 -0600
In article <9avqsa$6fugt$[EMAIL PROTECTED]>, [EMAIL PROTECTED]
says...
>
> "Tim Gahnstr�m /Bladerman" <[EMAIL PROTECTED]> schrieb im Newsbeitrag
> news:Z%CA6.4065$[EMAIL PROTECTED]...
>
> > Another thing. Are the numbers used in cryptografy usually so big
> > that I cannot assume that I know al the primes from 1 to the number
> > I am factoring? Or is that a "valid" asumption?
>
> You only need the primes from 2 to sqrt(the number you are factoring)
...but even that's FAR too many to consider trying to store.
--
Later,
Jerry.
The Universe is a figment of its own imagination.
------------------------------
From: [EMAIL PROTECTED] (David Wagner)
Subject: Re: Delta patching of encrypted data
Date: 11 Apr 2001 00:27:28 GMT
Reply-To: [EMAIL PROTECTED] (David Wagner)
Anon wrote:
>When my program encrypts the original file, I can chop it up into chunks.
>These can be any size I like - 4096 bytes, the Insel Intide hardware page is
>as good as any. I ship this file.
>
>Then I'm given another file at a later date. I don't have the original file
>available at this time. (this is the problem!)
I have to admit to being puzzled. Don't you have a copy of the
cryptographic key when you receive this file? If parties authorized
to change the file don't need to know the key, how are you going to
prevent unauthorized files from changing the file? If you're not
going to prevent unauthorized changes, i.e., you don't care about
message integrity at all, what is your application? I'm concerned:
Many people who think they don't need message integrity protection
turn out to simply not realize that they need it. Most likely I
misunderstood something somewhere along the chain of reasoning...
------------------------------
From: Steve Portly <[EMAIL PROTECTED]>
Subject: Re: Current best complexity for factoring?
Date: Tue, 10 Apr 2001 21:00:24 -0400
Jerry Coffin wrote:
> In article <9avqsa$6fugt$[EMAIL PROTECTED]>, [EMAIL PROTECTED]
> says...
> >
> > "Tim Gahnstr�m /Bladerman" <[EMAIL PROTECTED]> schrieb im Newsbeitrag
> > news:Z%CA6.4065$[EMAIL PROTECTED]...
> >
> > > Another thing. Are the numbers used in cryptografy usually so big
> > > that I cannot assume that I know al the primes from 1 to the number
> > > I am factoring? Or is that a "valid" asumption?
> >
> > You only need the primes from 2 to sqrt(the number you are factoring)
>
> ...but even that's FAR too many to consider trying to store.
>
> --
> Later,
> Jerry.
>
> The Universe is a figment of its own imagination.
When using RSA if you specify a larger key size, say 1024 bit key instead
of 512 bit is there any guarantee that one of the two primes won't be as
small as if a 512 bit key had been chosen? Are you always using primes
from different ranges?
------------------------------
From: [EMAIL PROTECTED] (David Moews)
Crossposted-To: sci.math
Subject: Re: Frobenius map over q-adic integers
Date: 10 Apr 2001 18:02:52 -0700
In article <9avrot$koi$[EMAIL PROTECTED]>,
Ian Goldberg <[EMAIL PROTECTED]> wrote:
|...p is a prime. q = p^d is a prime power.
|
|F_p and F_q are the finite fields with p and q elements, respectively.
|
|Z_p and Z_q are the rings of p-adic and q-adic integers, respectively
|(these have respectively F_p and F_q as subrings; let \pi be the
|projection map from Z_q to F_q).
|...
|Define the Teichmuller lift w : F_q -> Z_q as the function which
|maps x in F_q to the unique element z of Z_q such that
|\pi(z) = x, and z is a (q-1)th root of unity in Z_q.
|w is clearly multiplicative [w(x)w(y) is certainly a (q-1)th root
|of unity and \pi(w(x)w(y)) = xy, so w(x)w(y) = w(xy)]. w is *not*
|additive.
|
|Define the semi-Witt decomposition of x \in Z_q as the unique sequence
|(x_0, x_1, ...) of elements of F_q such that
| x = \sum_{i>=0} w(x_i)p^i
|Semi-Witt decompositions are neither multiplicative nor additive.
|
|It is straightforward to see that both these things are well-defined.
|
|Now here's the Frobenius map \Sigma: Z_q -> Z_q :
|
|Take x \in Z_q, and find its semi-Witt decomposition (x_0, x_1, ...).
|Take the little Frobenius map of each element (in F_q):
| ({x_0}^p, {x_1}^p, ...)
|\Sigma(x) is then the element of Z_q with *that* as its semi-Witt
| decomposition; i.e.
|
| \Sigma(x) = \sum_{i>=0} w({x_i}^p) p^i
| = \sum_{i>=0} {w(x_i)}^p p^i
|
|...WHY is \Sigma a ring automorphism on Z_q?
Let Q_q be the quotient field of Z_q, Q_p be the quotient field of Z_p,
and t be a primitive (q-1)st root of unity in Q_q. Then Q_q = Q_p(t)
is a field extension of Q_p. The conjugates of \pi(t) over F_p are
\pi(t), \pi(t)^p, ..., \pi(t)^{p^{d-1}}, and Hensel's Lemma implies that
the polynomial X^(q-1)-1 factors over Z_p in the same way as it does over F_p.
so the conjugates of t over Q_p are t, t^p, ..., t^{p^{d-1}}. Therefore
Q_q is a Galois extension of Q_p and it has an automorphism fixing Q_p
given by sending t to t^p. This is your \Sigma.
--
David Moews [EMAIL PROTECTED]
------------------------------
From: [EMAIL PROTECTED] (Mark Wooding)
Subject: Re: AES Inverse trick
Date: 11 Apr 2001 01:15:30 GMT
alex <[EMAIL PROTECTED]> wrote:
> Hello.
> I'm doing a project using Rijndael as the private key encryption
> algo. I'm following the steps provided in the AES.
> I've managed to create an algorithm capable of obtaining the
> Multiplicative inverse on GF(2^8) by using a version of the Extended
> euclidean algorithm.
> The process is however very very slow since it implies translating
> the number on GF(2^8) to a polynomial form and operating accordingly.
>
> I've seen through some previous posts to the newsgrop and various
> other papers, that they use a different and much easier process:
>
> for values of i > than 0 and < than 256
> log[pow[i] = j] = i
> where j = j XOR (j << 1) if j < 0x80
> j = j XOR (j <<1 ) ^ 0x11b if j > 0x80;
> ----------------------------------
> then:
> for values of i > than 1 and < 256
> j = pow[255 - log[i]]
> ....
> (not complete)
>
> I believe that the outcome of the previous operations does give out the
> Inverse.
>
> I've been unable to find a description of the previous process anywhere,
> and it will take away the point of the project to use a mathematical
> equation which i can't understand the base of.
>
> Would someone be kind enough to either explain to me what is the base of
> the previous or to give me some directions on where i can find the
> description for the process described above?.
>
> Thank you in advance.
> Alex
>
--
[mdw]
------------------------------
From: "Scott Fluhrer" <[EMAIL PROTECTED]>
Subject: Re: Current best complexity for factoring?
Date: Tue, 10 Apr 2001 18:33:15 -0700
Steve Portly <[EMAIL PROTECTED]> wrote in message
news:[EMAIL PROTECTED]...
>
>
> Jerry Coffin wrote:
>
> > In article <9avqsa$6fugt$[EMAIL PROTECTED]>, [EMAIL PROTECTED]
> > says...
> > >
> > > "Tim Gahnstr�m /Bladerman" <[EMAIL PROTECTED]> schrieb im Newsbeitrag
> > > news:Z%CA6.4065$[EMAIL PROTECTED]...
> > >
> > > > Another thing. Are the numbers used in cryptografy usually so big
> > > > that I cannot assume that I know al the primes from 1 to the number
> > > > I am factoring? Or is that a "valid" asumption?
> > >
> > > You only need the primes from 2 to sqrt(the number you are factoring)
> >
> > ...but even that's FAR too many to consider trying to store.
> >
> > --
> > Later,
> > Jerry.
> >
> > The Universe is a figment of its own imagination.
>
> When using RSA if you specify a larger key size, say 1024 bit key instead
> of 512 bit is there any guarantee that one of the two primes won't be as
> small as if a 512 bit key had been chosen? Are you always using primes
> from different ranges?
Normally, when you create an RSA private/public keypair, you select the
primes, the public exponent, and then use that to form the public key.
Since you are the one selecting the primes, you get to chose their relative
sizes.
--
poncho
------------------------------
From: "Simon Johnson" <[EMAIL PROTECTED]>
Subject: Re: Dickson Polynomials?
Date: Wed, 11 Apr 2001 03:00:38 +0100
Mark Wooding <[EMAIL PROTECTED]> wrote in message
news:[EMAIL PROTECTED]...
> Tom St Denis <[EMAIL PROTECTED]> wrote:
>
> > Yeah I should learn latex, and the ascii art isn't legible due to a
> > non-fixed width font. What would be cool is a free tool where you can
copy
> > paste that stuff and see what it is.....
>
> Ah. Now what you're asking for is a newsreader which isn't hopelessly
> deficient. There are plenty of these.
*grin*
Simon.
> -- [mdw]
------------------------------
From: "Simon Johnson" <[EMAIL PROTECTED]>
Subject: Re: MIPS Ratings for Encryption Algorithms
Date: Wed, 11 Apr 2001 03:15:32 +0100
Chuck Perry <[EMAIL PROTECTED]> wrote in message
news:[EMAIL PROTECTED]...
> Is there a web site or other such source that has done something like
> this for various platforms (i.e. TMS320 DSPs)?
>
> I'm interested in ratings for SHA-1 and 3DES-CBC. Also for some of the
> ECC digital signing per the latest version of IEEE 1394.
>
> Thanks,
> Chuck
>
Algorithm speeds are usually normalised into the number of clock cycles per
[suitable data-size unit here]... I personally haven't seen MIPS ratings for
encryption algorithms.
Simon.
------------------------------
** 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
******************************
