Cryptography-Digest Digest #377, Volume #13 Thu, 21 Dec 00 20:13:01 EST
Contents:
Re: All irreducible polys of degree 32 over GF(2) ("Matt Timmermans")
RE: Q: Result of an old thread? (Bryan Olson)
Re: Javascript Implementation of Block Cipher (Darren New)
RE: Q: Result of an old thread? ("Manuel Pancorbo")
Re: does CA need the proof of acceptance of key binding ? ("Lyalc")
Re: All irreducible polys of degree 32 over GF(2) (Bryan Olson)
Re: Steganography using text as carrier (Andre van Straaten)
Algorithm for check SAC complience (Simon Johnson)
Re: cipher algorithms once again... ("maciek")
Re: cipher algorithms once again... ("maciek")
Re: AES (Rijndael) DLL ("Brian Gladman")
Re: Steganography using text as carrier ([EMAIL PROTECTED])
Re: Unguessable sequence of unique integers? ([EMAIL PROTECTED])
Re: Steganography using text as carrier (Andre van Straaten)
----------------------------------------------------------------------------
From: "Matt Timmermans" <[EMAIL PROTECTED]>
Subject: Re: All irreducible polys of degree 32 over GF(2)
Date: Thu, 21 Dec 2000 19:18:49 GMT
"Mike Rosing" <[EMAIL PROTECTED]> wrote in message
news:[EMAIL PROTECTED]...
> [...] This works because x^2^r - x
> contains all possible irreducible factors of degree r
> [...]
Thanks, Mike. That will do nicely.
------------------------------
From: Bryan Olson <[EMAIL PROTECTED]>
Subject: RE: Q: Result of an old thread?
Date: Thu, 21 Dec 2000 19:15:14 GMT
Manuel Pancorbo wrote:
> If you work with matrices with integer coefficients modulo N,
> where N = pq being {p,q} primes, the matrix Y is very hard to
> find, unless you have also {p,q}.
>
> This is because at some step you must perform single number
> inverse operations modulo N, which is rather difficult
> without {p,q}.
Not true. The extended Euclidean algorithm finds modular
inverses efficiently (when they exist). You can look it up in
most algorithms books, or in HAC.
Here it is in Python:
| def inverse(x, n):
| """Returns the mod n inverse of x.
| """
| y, a, b = n, 1, 0
| while y>0:
| x, (q, y) = y, divmod(x, y)
| a, b = b, a - b*q
| if a < 0:
| a = a + n
| assert x == 1, "No inverse; GCD is %d" % x
| return a
--Bryan
Sent via Deja.com
http://www.deja.com/
------------------------------
From: Darren New <[EMAIL PROTECTED]>
Subject: Re: Javascript Implementation of Block Cipher
Date: Thu, 21 Dec 2000 20:35:07 GMT
Paul Rubin wrote:
> Why do you need a block cipher? Implementing RC4 in javascript is
> very easy.
Even easier - it's already done.
http://www.leemon.com/crypto/SelfDecrypt.html
--
Darren New / Senior MTS & Free Radical / Invisible Worlds Inc.
San Diego, CA, USA (PST). Cryptokeys on demand.
Personal malapropism generator free with purchase!
Steganography: The manual is hidden in the source code.
Gold mining is only profitable because of the gold found.
------------------------------
From: "Manuel Pancorbo" <[EMAIL PROTECTED]>
Subject: RE: Q: Result of an old thread?
Date: Thu, 21 Dec 2000 21:43:38 +0100
"Walter Hofmann" <[EMAIL PROTECTED]>
> On Tue, 19 Dec 2000 01:31:16 +0100, Manuel Pancorbo <[EMAIL PROTECTED]>
wrote:
> >"Walter Hofmann"
> >> You don't need p,q to do any of the computations above.
> >>
> >
> >Alice needs p,q to compute A^-1, because (det A)^-1 mod N is needed.
>
> This can easily be done without p and q. Use Euklid's algorithm.
>
Walter and Bryan are right. I've got confused with the mathematical
properties of finite groups.
--
____________________________________________________________________
Manuel Pancorbo
[EMAIL PROTECTED] (Apply ROT13)
____________________________________________________________________
------------------------------
From: "Lyalc" <[EMAIL PROTECTED]>
Subject: Re: does CA need the proof of acceptance of key binding ?
Date: Fri, 22 Dec 2000 08:08:35 +1100
Indeed it is feasible.
May require a physical visit to the branch with public key and proof of
risghts to access certain bank accounts.
It's what X.59 is about - a 2 party digital signature relationship.
Most high value commercial relationships occur between only 2 parties, or
groups of 2 parties - buying a house means a buyer-seller relationship, with
another, discrete buyer-bank relationship.
Posssibly the most important relationship is the buyer-bank.
This opens up a few areas where heirarchical PKI has massive commercial
challenges
- convincing potential participants that every relationship must have
similar trust,
- then expecting only one party (e.g. a bank) to pay for most of the
infrastructure, and
- trying to establish commercial trust in parallel to a technology chain of
events.
Lyal
Mok-Kong Shen wrote in message <[EMAIL PROTECTED]>...
>
>
>Anne & Lynn Wheeler wrote:
>>
>> there are all sorts of boundary & discontinuity conditions.
>......
>[snip]
>
>Dumb question: Is it that difficult/impractical for
>a customer to deposit a public key at his bank and
>be able to sign all kinds of stuffs, thus avoiding
>the sort of problems discussed in this thread?
>
>M. K. Shen
------------------------------
From: Bryan Olson <[EMAIL PROTECTED]>
Subject: Re: All irreducible polys of degree 32 over GF(2)
Date: Thu, 21 Dec 2000 21:17:45 GMT
David Wagner wrote:
> Bryan Olson wrote:
> >Can anyone come up with a sub-quadratic method?
>
> Sure. Here's one that runs in linear time.
>
> Each sender picks a random 32-bit word of the file, and
> sends that word as well as the offset of that word in
> the file. For a file of length N, c*N bits of
> communication will suffice (for some not-too-large
> constant > c with c>1).
Can you show why? The question seems to be how many tries it
takes to select all of n slots, if each try chooses one of the
slots uniformly with replacement.
I had figured that when there are m of the n slots full, the
expected number of tries to choose an empty slot by choosing
slots uniformly is n/(n-m). The expected value of the sum is
the sum of the expected values. If we add the expected number
of tries to fill each slot in the order in which they are
filled, we get:
n/n + n/(n-1) + n/(n-2) + ... + n/1
= n (1 + 1/2 + 1/3 + ... + 1/n)
= n (ln(n) + O(1))
= Theta(n ln(n))
Is there some reason that the above is invalid?
--Bryan
Sent via Deja.com
http://www.deja.com/
------------------------------
From: Andre van Straaten <[EMAIL PROTECTED]>
Subject: Re: Steganography using text as carrier
Date: 21 Dec 2000 15:58:38 -0600
[EMAIL PROTECTED] wrote:
> In article <[EMAIL PROTECTED]>,
> Andre van Straaten <[EMAIL PROTECTED]> wrote:
>> [EMAIL PROTECTED] wrote:
>> > compare any text (T) to any desired carrier text, (C) character to
>> > character, and the difference between the the character in (T) and
> the
>> > character in (C) can be represented by a number
>> > [using positive integers only, ~ e.g. if the character <d> in T is
>> > represented by 100, and the character <b> in C is represented by 98,
>> > the difference would be represented by the number 298 {300-100+98}
> not
>> > by the number 2]
>>
>> > the offset between any text T and any carrier C, will be able to be
>> > expressed as a string of three digit integers, resulting in one very
>> > large integer , which can be expressed as an MPI.
>>
>> Sorry, no clue what is an MPI. Without that, I have problems to
>> understand your idea at all.
> an MPI is a Multi Precision Integer, commonly used in pgp and other
> cryptographic implementations, see the revised rfc 2440:
> http://www.imc.org/draft-ietf-openpgp-rfc2440bis
> "...
> 3.2. Multi-Precision Integers
> Multi-Precision Integers (also called MPIs) are unsigned integers
> used to hold large integers such as the ones used in cryptographic
> calculations.
> An MPI consists of two pieces: a two-octet scalar that is the length
> of the MPI in bits followed by a string of octets that contain the
> actual integer.
> These octets form a big-endian number; a big-endian number can be
> made into an MPI by prefixing it with the appropriate length..."
> what the MPI accomplishes is to represent a very large integer in a
> short notation so that it can be sent easily {and hopefully
> steganographically 'hidden' easily } and then reconstructed back into
> the very large actual integer when necessary.
> in the above proposed scheme, any text can be represented as a series
> of three digit integers.
> when two texts are compared looking at the three digit integer
> groupings in one text, and the corresponding three digtit integer
> grouping in the other text, a three digit integer 'offset' can easily
> be generated, describing exactly how one can be transformed into the
> other. When these three digit integers representing the offset
> difference between the two texts are viewed as a long series of three
> digit integers, one next to the other without any intervening spaces,
> they constitute one very long integer.
> This very long integer is the key how any plaintext can be transformed
> into any carrier text and back into the same plaintext.
I'm too lazy now for some ASCII calculus, but I understand it this way:
e.g.
100 bytes plaintext and 100 bytes carriertext give
100 three-digit integers, packed into one MPI number.
> When this integer is represented as an MPI, it is a relatively short
> string, that if it could somehow be hidden within the carrier text,
> it would allow for steganographic hiding of text within text, without
> restriction on the length of the texts.
I think the shortness of the MPI depends on the shortness of the plaintext,
and is "relatively short" on for a large ratio of carriertext through
plaintext.
And hiding it "somehow" jeopardizes the steganographic value of the
carriertext.
>> But it looks to me that it's not only an algorithm for steganography
>> but for encrypting, too.
> yes,
> an alternative to key-based encryption, and not dependent on the
> (hopefully, very unlikely) possiblity of breaktroughs in the
> underlying 'mathematical problems' basis of public key encryption
> schemes.
> the security depends only on the agreement of the initial carrier text,
If agreement means that both parties must have an initial, unaltered copy
of the carriertext to compare it with the transmitted carriertext, then it
is a cumbersome key management.
I think also, that the security suffers from the attempt to bring in
steganography. As the key is part of the message, the more random the
carriertext is, the more difficult to identify the possible bits altered
by the MPI string.
If you use sensible text, the alterations are very obvious.
> {ideally, as random as possible, and changed after each message, with
> the instructions for the next carrier text to be used, included in the
> previous message,
Well, finally it ends up with no steganography at all, then?
And putting the instructions for the next carrier into the actual message
gives a chain of dependencies which can be exploited.
> also, if used for encryption, the carrier text should be longer than
> the plain text, otherwise the end of the plaintext can easily be
> reconstructed by an attacker just from the MPI, without knowing the
> carrier text}
> hope this is clearer,
Not really sure, if I understood it the right way. There is left the
question how to embed the MPI string into the carriertext.
Then, is there a list of carriertexts which both parties have? How is
the notification about the next carriertext.
It looks to me much as a variation of the OTP. The only difference or
improvement: The key is embedded together with the message in a larger
carrier text (which on the other side weakens the security).
The great disadvantage is for the OTP the transmission of various pads
of message size, or in your case, various carrier texts.
-- avs
Andre van Straaten
http://www.vanstraatensoft.com
The signs and the omens are everywhere
But too few see them - too few even care
(Lee Clayton - singer/songwriter, 1979)
====== Posted via Newsfeeds.Com, Uncensored Usenet News ======
http://www.newsfeeds.com - The #1 Newsgroup Service in the World!
======= Over 80,000 Newsgroups = 16 Different Servers! ======
------------------------------
From: Simon Johnson <[EMAIL PROTECTED]>
Subject: Algorithm for check SAC complience
Date: Thu, 21 Dec 2000 22:05:13 GMT
The topic basically states the question?
In websites i should visit?
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: "maciek" <[EMAIL PROTECTED]>
Subject: Re: cipher algorithms once again...
Date: Thu, 21 Dec 2000 23:32:12 +0100
Thanks alot John. You've got real nice site. I think I'll find there answers
to most of my questions :-)
Maciek
> Visit my web site; several algorithms in current use, such as DES,
> Rijndael, IDEA, Blowfish, and others, are fully described in detail
> there, along with clear explanatory diagrams.
>
> John Savard
> http://home.ecn.ab.ca/~jsavard/crypto.htm
------------------------------
From: "maciek" <[EMAIL PROTECTED]>
Subject: Re: cipher algorithms once again...
Date: Thu, 21 Dec 2000 23:32:54 +0100
Thanks alot for replies, guys!
Maciek
"maciek" <[EMAIL PROTECTED]> wrote in message news:91r328$bof$[EMAIL PROTECTED]...
> Thanks for answer.
>
> So there are two groups which are pratically used these days: block and
> stream ciphers, am I right?
>
> If I had to name, let's say ten mostly used algorithms, what would be the
> right order?
>
> > Block Algorithms:
> >
> > Blowfish
> > Twofish
> > Cast
> > IDEA
> > FEAL
> > RC5
> > RC6
> >
> > Stream-Cipher:
> >
> > RC4
> > Seal
> > Self-Shrinking Linear Feedback Shift Registers.
> > Fish
> > PKZip (woefully insecure, but its used in Winzip)
> > WAKE
> > Blum-Blum Shub
>
>
>
------------------------------
From: "Brian Gladman" <[EMAIL PROTECTED]>
Subject: Re: AES (Rijndael) DLL
Date: Thu, 21 Dec 2000 22:40:53 -0000
"Brian Gladman" <[EMAIL PROTECTED]> wrote in message
news:ZEv%5.22396$I5.244814@stones...
> For those who wish to play with AES (Rijndael) from Visual Basic, I have
now
> updated my code at:
>
> http://fp.gladman.plus.com/cryptography_technology/rijndael/index.htm
>
> to produce a DLL version at:
>
> http://fp.gladman.plus.com/cryptography_technology/rijndael/aes.dll
For Visual Basic (VB) fans I have just published a VB interface
specification for this dll. I tested this in VBA (I don't have VB) but I
think it will work equally well in VB.
You will need the updated DLL as well since the earlier version was correct
for C/C++ use but was not in the DLL format required for calls from VB code.
Brian Gladman
------------------------------
From: [EMAIL PROTECTED]
Subject: Re: Steganography using text as carrier
Date: Thu, 21 Dec 2000 23:00:26 GMT
In article <[EMAIL PROTECTED]>,
Andre van Straaten <[EMAIL PROTECTED]> wrote:
> Steganography is to hide your plain- or ciphertext at all. It's like
> camouflage. It's like crossing a border illegally. Being seen means
> the end of the game.
> The problem here is, how distrustfully is the adversary to distinguish
> the hidden object from the environment.
> A company which transmits a lot of information can easier add some
> hidden information than a private person which starts suddenly
> interchanging large texts of Shakespeare or other stuff which makes
> no sense.
point of the proposed scheme is that the message text can be disguised
in 'any' e-mail text, size independent.
it is not necessary to send large blocks of obscure text.
assume that the carrier text is 1kb (can be much less too) of any text
message,
assume that the message text to be hidden is 20 kb,
the algorithm would just assume that the carrier text has an additional
19kb of 'empty space' and generate the 3 digit integer string for empty
space for another 19kb, compute the offset between the two texts,
generate the MPI for the offset,
Now, {and this is the part i don't know how to do yet } if this MPI
could be hidden in the carrier text by somehow 'marking' individual
characters in the carrier text, then the message text is effectively
steganographically hidden.
{The message text should be encrypted textblock if the carrier text is
an open e-mail message.}
> > all that would be necessary is the agreement (in advance) between
Bob
> > and Alice on the initial carrier text,
> > e.g., a certain page of a specific text that both have access to.
>
> This looks like that it's use is limited to occasional traffic. This
> agreement in advance needs a separate algorithm or scheme, then?
does need an algorithm of converting the message text to and from the
carrier text, but is not limited in size or frequency of traffic.
> > then Bob can type a long text of (pseudo)random keyboard characters,
> > generate the MPI of the offset of this new text of gibberish
characters
> > and the agreed upon carrier text, send the MPI to Alice, with the
> > understanding that the resultant gibberish text be used as the
carrier
> > text for further communications, and then periodically change the
> > carrier texts in a similar manner.
>
> To what extent the resulting text for mailing looks like gibberish?
>
If this scheme is to be used for encryption, not steganography,
then it is less effective if there is a carrier text in plain language,
as the MPI representing the offset between the carrier text and
message text, may be subject to frequency cryptanalysis.
the proposal is, that once a convenient plaintext carrier is agreed
upon by Bob and Alice, Bob can then generate a gibberish text [to use
as the carrier for the *next* message conveying 'real information'].
the exact 'gibberish text' is transmitted to Alice in the form of an
MPI, which when applied to their initial agreed-upon carrier text,
generates the 'gibberish text' that both will use for their next
carrier for the next message.
The actual message sent is not gibberish, just an MPI represntation,
useless to an attacker without knowing the carrier text it refers to.
any attacker intercepting the MPI will not be able to reconsrtuct the
message.
Once a random (or close to random) carrier text is used, there is no
possible effective 'brute force' or other method to find the original
message,
since, for example, messages of <a=b>, and <a does not = b>, are
equally likely for the same MPI, depending on which carrier text is
used.
sorry if i have not conveyed this clearly,
hopefully, if the book you mentioned would provide a way to hide a
small amount of information in a text message,
i would be able to give a concrete example from beginning to end,
thanks again,
vedaal
Sent via Deja.com
http://www.deja.com/
------------------------------
From: [EMAIL PROTECTED]
Subject: Re: Unguessable sequence of unique integers?
Date: Thu, 21 Dec 2000 23:55:22 GMT
Ok I'm kinda late to the party, but it's really not that hard. If I
understand correctly what you want is a ring RNG. That's easy, and
here's how you do it.
pick a 32-bit number, one close to 2^32, and based on what you said at
least 2^24, call it N, compute it's factorization
choose a value e, it must be prime relative to phi(N) for which you can
use the factorization
Maintain a counter, call it M.
To compute the output value X, compute the value X=M^e mod N
The output will have 0 collisions until M reaches the value of N
If you want a proof of security, that too is easy. This is the RSA
equation, with hidden modulus and hidden public exponent.
The attacker will have very nearly 0 knowledge, and if you're pushing
close to sqrt(N) you should use a larger modulus for safety, but it's
not completely necessary.
Joe
Sent via Deja.com
http://www.deja.com/
------------------------------
From: Andre van Straaten <[EMAIL PROTECTED]>
Subject: Re: Steganography using text as carrier
Date: 21 Dec 2000 18:10:04 -0600
[EMAIL PROTECTED] wrote:
> In article <[EMAIL PROTECTED]>,
> Andre van Straaten <[EMAIL PROTECTED]> wrote:
>> Steganography is to hide your plain- or ciphertext at all. It's like
>> camouflage. It's like crossing a border illegally. Being seen means
>> the end of the game.
>> The problem here is, how distrustfully is the adversary to distinguish
>> the hidden object from the environment.
>> A company which transmits a lot of information can easier add some
>> hidden information than a private person which starts suddenly
>> interchanging large texts of Shakespeare or other stuff which makes
>> no sense.
> point of the proposed scheme is that the message text can be disguised
> in 'any' e-mail text, size independent.
> it is not necessary to send large blocks of obscure text.
> assume that the carrier text is 1kb (can be much less too) of any text
> message,
> assume that the message text to be hidden is 20 kb,
> the algorithm would just assume that the carrier text has an additional
> 19kb of 'empty space' and generate the 3 digit integer string for empty
> space for another 19kb, compute the offset between the two texts,
> generate the MPI for the offset,
I don't see an advantage over an OTP. You transpose the ASCII characters
in a constant way into a proprietary number scheme and generate finally
an MPI string out of an operation of two texts.
Security is given only by applying an operation between a unique plaintext
and a unique key text.
I suggest you give a short example with your translation of characters
and your operation which applies.
I doubt that you can hide a text within a large amount of empty space,
because you apply always the operation with the same empty space
character.
An OTP uses generally the ASCII character set with the XOR operation.
Give a short example with your character set, or part of it, using your
operation, please.
An example of a message of 10 - 15 characters will do it.
> Now, {and this is the part i don't know how to do yet } if this MPI
> could be hidden in the carrier text by somehow 'marking' individual
> characters in the carrier text, then the message text is effectively
> steganographically hidden.
> {The message text should be encrypted textblock if the carrier text is
> an open e-mail message.}
>> > all that would be necessary is the agreement (in advance) between
> Bob
>> > and Alice on the initial carrier text,
>> > e.g., a certain page of a specific text that both have access to.
>>
>> This looks like that it's use is limited to occasional traffic. This
>> agreement in advance needs a separate algorithm or scheme, then?
> does need an algorithm of converting the message text to and from the
> carrier text, but is not limited in size or frequency of traffic.
>> > then Bob can type a long text of (pseudo)random keyboard characters,
>> > generate the MPI of the offset of this new text of gibberish
> characters
>> > and the agreed upon carrier text, send the MPI to Alice, with the
>> > understanding that the resultant gibberish text be used as the
> carrier
>> > text for further communications, and then periodically change the
>> > carrier texts in a similar manner.
>>
>> To what extent the resulting text for mailing looks like gibberish?
>>
> If this scheme is to be used for encryption, not steganography,
> then it is less effective if there is a carrier text in plain language,
> as the MPI representing the offset between the carrier text and
> message text, may be subject to frequency cryptanalysis.
> the proposal is, that once a convenient plaintext carrier is agreed
> upon by Bob and Alice, Bob can then generate a gibberish text [to use
> as the carrier for the *next* message conveying 'real information'].
> the exact 'gibberish text' is transmitted to Alice in the form of an
> MPI, which when applied to their initial agreed-upon carrier text,
> generates the 'gibberish text' that both will use for their next
> carrier for the next message.
> The actual message sent is not gibberish, just an MPI represntation,
> useless to an attacker without knowing the carrier text it refers to.
> any attacker intercepting the MPI will not be able to reconsrtuct the
> message.
> Once a random (or close to random) carrier text is used, there is no
> possible effective 'brute force' or other method to find the original
> message,
> since, for example, messages of <a=b>, and <a does not = b>, are
> equally likely for the same MPI, depending on which carrier text is
> used.
> sorry if i have not conveyed this clearly,
> hopefully, if the book you mentioned would provide a way to hide a
> small amount of information in a text message,
> i would be able to give a concrete example from beginning to end,
This book is mainly about steganography, and it generates messages in
that way that it breaks up sentences in its grammatical parts and
constructs new sentences depending on the plaintext input like:
Bob drives to Washington, D.C.
Alice is driving to New York.
Carol arrives tomorrow in New York.
I don't see a way to hide a message within a text message by adding
or changing some bits in a byte as it is done with graphic files.
If you change only one bit in an ASCII file you have another character,
i.e. a typo.
You could use another set of characters with a wider range of possible
characters, instead of 256 you could 64 kB. But this representation
doesn't fit in any ASCII or HTML application.
You cannot disguise an elephant as a mouse.
That's why steganography is in most cases with large binary files.
-- avs
Andre van Straaten
http://www.vanstraatensoft.com
The signs and the omens are everywhere
But too few see them - too few even care
(Lee Clayton - singer/songwriter, 1979)
====== Posted via Newsfeeds.Com, Uncensored Usenet News ======
http://www.newsfeeds.com - The #1 Newsgroup Service in the World!
======= Over 80,000 Newsgroups = 16 Different Servers! ======
------------------------------
** 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
******************************
