Cryptography-Digest Digest #271, Volume #14 Mon, 30 Apr 01 14:13:00 EDT
Contents:
Re: request for encryption software suggestions (yomgui)
Re: A Question Regarding Backdoors ("Terry")
Re: Thames Bridge Cipher ("ben")
Re: Thames Bridge Cipher ("ben")
Re: request for encryption software suggestions ("Tom St Denis")
Re: request for encryption software suggestions (yomgui)
Re: request for encryption software suggestions (yomgui)
Re: request for encryption software suggestions ("Tom St Denis")
Message mapping in EC. ("Cristiano")
Re: request for encryption software suggestions (yomgui)
Q: Searching for a free OCSP implementation (Tomas Perlines Hormann)
Re: A Question Regarding Backdoors (SCOTT19U.ZIP_GUY)
Re: A Question Regarding Backdoors ("Tom St Denis")
Re: request for encryption software suggestions (Charles Blair)
Re: Quantum Crypto (Bill Unruh)
Re: A keen symmetric cipher idea (newbie)
Re: A keen symmetric cipher idea (newbie)
Re: A Question Regarding Backdoors (Mok-Kong Shen)
Re: Censorship Threat at Information Hiding Workshop (Bill Unruh)
Re: RSA BRUTE FORCE (Bill Unruh)
Re: Censorship Threat at Information Hiding Workshop (Leonard R. Budney)
Re: A keen symmetric cipher idea (David Wagner)
Re: RSA BRUTE FORCE (Erictim)
Re: DSA in GF(2^W)? (Mike Rosing)
----------------------------------------------------------------------------
From: yomgui <[EMAIL PROTECTED]>
Subject: Re: request for encryption software suggestions
Date: Mon, 30 Apr 2001 14:46:13 +0100
free, small, cross platform, safe, simple, fast, open source,
symetric stream and file encryption
http://bigfoot.com/~kryptyomic
Eric Kleinberg wrote:
>
> I am seeking freeware C source which can encrypt a buffer and whose output
> is a buffer of the same size. The encryption does not have to be very
> strong.
>
> Any suggestions (URLs) would be appreciated.
--
¥øµgüí
oim 3d - surface viewer - http://i.am/oim
kryptyomic - encryption scheme - http://bigfoot.com/~kryptyomic
------------------------------
From: "Terry" <[EMAIL PROTECTED]>
Subject: Re: A Question Regarding Backdoors
Date: Tue, 1 May 2001 00:00:23 +1000
There is another new group named talk.policits.crypto. Ther might be some
people there (who are not here) that might have some usefull info too.
-Terry Tollisen
------------------------------
From: "ben" <[EMAIL PROTECTED]>
Subject: Re: Thames Bridge Cipher
Date: Mon, 30 Apr 2001 15:05:50 +0100
> Most information on that algorithm is classified - you will find no useful
> information without proper clearance.
I thought that might be the case - it's the approved algorithm where I work,
and I was curious to know more about it.
> Considering that the algorithms have been implemented in "nearly off the
> shelf packages" I'm surprised that information hasn't yet been leaked.
Me too! Thanks for the reply,
ben
------------------------------
From: "ben" <[EMAIL PROTECTED]>
Subject: Re: Thames Bridge Cipher
Date: Mon, 30 Apr 2001 15:06:23 +0100
> Thames Bridge is a UK government cipher the details of which have never
been
> published as far as I know. It is made available to manufatcurers of
> commercial security products under confidentiality agreements so that it
can
> be incorporated into special variants of their products for UK government
> use.
Thanks for the reply - I had a feeling that would be the case...
ben
------------------------------
From: "Tom St Denis" <[EMAIL PROTECTED]>
Subject: Re: request for encryption software suggestions
Date: Mon, 30 Apr 2001 14:28:03 GMT
"yomgui" <[EMAIL PROTECTED]> wrote in message
news:[EMAIL PROTECTED]...
> free, small, cross platform, safe, simple, fast, open source,
> symetric stream and file encryption
>
> http://bigfoot.com/~kryptyomic
I would avoid this like the plague. I looked at the source and as far as I
can tell it's some home brew cipher design.
Not only that but they spell "symetric" [sic] wrong.
Tom
------------------------------
From: yomgui <[EMAIL PROTECTED]>
Subject: Re: request for encryption software suggestions
Date: Mon, 30 Apr 2001 15:48:24 +0100
Tom St Denis wrote:
>
> I would avoid this like the plague. I looked at the source and as far as I
> can tell it's some home brew cipher design.
could you please be more precise tell me what you don't like in it ?
> Not only that but they spell "symetric" [sic] wrong.
it is the right way on my side of the planet.
thanks
yomgui
------------------------------
From: yomgui <[EMAIL PROTECTED]>
Subject: Re: request for encryption software suggestions
Date: Mon, 30 Apr 2001 15:54:08 +0100
yomgui wrote:
>
> > Not only that but they spell "symetric" [sic] wrong.
you are right. symmetric (just one m in french)
------------------------------
From: "Tom St Denis" <[EMAIL PROTECTED]>
Subject: Re: request for encryption software suggestions
Date: Mon, 30 Apr 2001 14:58:50 GMT
"yomgui" <[EMAIL PROTECTED]> wrote in message
news:[EMAIL PROTECTED]...
> Tom St Denis wrote:
> >
> > I would avoid this like the plague. I looked at the source and as far
as I
> > can tell it's some home brew cipher design.
>
> could you please be more precise tell me what you don't like in it ?
Well for starters you call substitution tables "grids", and your cipher is
not a known one, it's a home brew which means it most likely hasn't been
analyzed. Why not describe it clearly here so we can take alook at it.
Tom
------------------------------
From: "Cristiano" <[EMAIL PROTECTED]>
Subject: Message mapping in EC.
Date: Mon, 30 Apr 2001 17:08:05 +0200
I have translated an algorithm for blind signature in DL to works in EC. The
problem is to map any message in a point of the elliptic curve. Is there any
way?
Is there some precaution to take for be sure that the algorithm in EC
doesn't have some weakness?
Thanks
Cristiano
------------------------------
From: yomgui <[EMAIL PROTECTED]>
Subject: Re: request for encryption software suggestions
Date: Mon, 30 Apr 2001 16:35:15 +0100
Tom St Denis wrote:
>
> Why not describe it clearly here so we can take alook at it.
after shuffling a bit the method
that generate pseudo random numbers
the encryption is performed here:
val0
val1 = val0 XOR [a pseudo random number]
val2 = SubstitutionTable [ val1 ]
val3 = val2 XOR [the same pseudo random number]
it could be replace by a simple XOR,
but I choose that,
I don't think it's less secure.
thanks for looking at it.
--
¥øµgüí
oim 3d - surface viewer - http://i.am/oim
kryptyomic - encryption scheme - http://bigfoot.com/~kryptyomic
------------------------------
From: Tomas Perlines Hormann <[EMAIL PROTECTED]>
Crossposted-To: comp.security.misc
Subject: Q: Searching for a free OCSP implementation
Date: Mon, 30 Apr 2001 17:32:52 +0200
Hi,
I am currently working on my master's thesis about SignedContent and
need an implementation of the "Online Certificate Status Protocol
(OCSP)" as specified in IETF RFC 2560.
My purpose is to evaluate different certificate validation techniques
within a PKI.
Does anybody know of a free implementation? I would be very grateful if
anybody could direct me to some freely available implementations.
Thanks a lot in advance.
--
Tomás Perlines Hormann
------------------------------
From: [EMAIL PROTECTED] (SCOTT19U.ZIP_GUY)
Subject: Re: A Question Regarding Backdoors
Date: 30 Apr 2001 15:29:38 GMT
aquiranNO$[EMAIL PROTECTED] (Arturo) wrote in
<[EMAIL PROTECTED]>:
>On Mon, 30 Apr 2001 02:20:21 GMT, [EMAIL PROTECTED] (bob) wrote:
>
> AES candidates have been scrutinized and are open for everybody to
> see,
>so I doublt Rijndael could have any backdoor without anybody realizing
>it. I certainly don´t think that a backdoor was included in AES
>requirements.
>
>
I think if you took a straight ascii message and encrypted with
standard Rijndael then the NSA could break it. If they couldn't break
it. Then they wouldn't allow the US government to encourage others
to use it. The back door in Rijndael is that they know a fast way to
reverse it. However certain things can make it harder such as using
bijective compresses first as in Matts BICOM
David A. Scott
--
SCOTT19U.ZIP NOW AVAILABLE WORLD WIDE "OLD VERSIOM"
http://www.jim.com/jamesd/Kong/scott19u.zip
My website http://members.nbci.com/ecil/index.htm
My crypto code http://radiusnet.net/crypto/archive/scott/
MY Compression Page http://members.nbci.com/ecil/compress.htm
**NOTE FOR EMAIL drop the roman "five" ***
Disclaimer:I am in no way responsible for any of the statements
made in the above text. For all I know I might be drugged or
something..
No I'm not paranoid. You all think I'm paranoid, don't you!
------------------------------
From: "Tom St Denis" <[EMAIL PROTECTED]>
Subject: Re: A Question Regarding Backdoors
Date: Mon, 30 Apr 2001 16:36:17 GMT
"SCOTT19U.ZIP_GUY" <[EMAIL PROTECTED]> wrote in message
news:[EMAIL PROTECTED]...
> aquiranNO$[EMAIL PROTECTED] (Arturo) wrote in
> <[EMAIL PROTECTED]>:
>
> >On Mon, 30 Apr 2001 02:20:21 GMT, [EMAIL PROTECTED] (bob) wrote:
> >
> > AES candidates have been scrutinized and are open for everybody to
> > see,
> >so I doublt Rijndael could have any backdoor without anybody realizing
> >it. I certainly don´t think that a backdoor was included in AES
> >requirements.
> >
> >
>
> I think if you took a straight ascii message and encrypted with
> standard Rijndael then the NSA could break it. If they couldn't break
> it. Then they wouldn't allow the US government to encourage others
> to use it. The back door in Rijndael is that they know a fast way to
> reverse it. However certain things can make it harder such as using
> bijective compresses first as in Matts BICOM
You claim the NSA can do things... that seems very childish to me.
Tom
------------------------------
Subject: Re: request for encryption software suggestions
From: [EMAIL PROTECTED] (Charles Blair)
Date: Mon, 30 Apr 2001 16:41:26 GMT
The original poster specified same size output and did not have to
be very strong. Would rot-13 be acceptable?
------------------------------
From: [EMAIL PROTECTED] (Bill Unruh)
Subject: Re: Quantum Crypto
Date: 30 Apr 2001 16:49:30 GMT
In <D6PG6.740$[EMAIL PROTECTED]> "Roger Schlafly"
<[EMAIL PROTECTED]> writes:
>"Bill Unruh" <[EMAIL PROTECTED]> wrote
>> ]I don't believe either of the above statements is true. Usually QC
>systems
>> ]are some sort of combination of QC with conventional crypto, and
>> ]offering less security than is commonly offered by conventional crypto.
>> On what basis? QC uses conventional crypto. QC is used to generate a
>> random shared key between the two parties. A key which is known with
>> high probability not to have been eavesdropped. HOw is this less
>> security than is commonly offered by conventional crypto?
>Typically QC systems offer no promise at all that an individual bit
>might have been eavesdropped. Many conventional crypto systems
They offer the promise that that eavesdropping can be detected with a
25% probability ( actually slightly higher for some versions) . Also the
attacker will not know if he has the correct bit with a 25% probablity
as well (more with advanced systems).
>are designed with an attitude that the loss of one secret bit could
>be catastrophic.
So? This is designed differently. QC is a key exchange mechanism. If you
are using a one bit key, it is stupid to use QC. If youare using a 1000
bit key, the probablility of not detecting the eavesdropping is
2^-1000 or so (or it can be made arbitrarily larger)
------------------------------
From: newbie <[EMAIL PROTECTED]>
Subject: Re: A keen symmetric cipher idea
Date: Mon, 30 Apr 2001 12:49:34 -0300
Who is stupid?
Tom St Denis wrote:
>
> "David Wagner" <[EMAIL PROTECTED]> wrote in message
> news:9cj24j$m4f$[EMAIL PROTECTED]...
> > Tom St Denis wrote:
> > >1. Both users pick two large primes p and q, then form N = pq
> > >2. To encode a message you take 0 < M < N and do, c1 = M mod p, c2 =
> > >M mod q
> >
> > This is utterly silly.
> >
> > p divides M - c1, so if you have two known plaintexts (M,(c1,c2)),
> > (M',(c1',c2')), then you can recover p as gcd(M - c1, M' - c1').
> >
> > You might want to study a bit more number theory before proposing any
> > more such ciphers.
>
> I agree. However my Koblitz book has not arrived and my "Dover Series"
> number theory books don't cover much of this type of math.
>
> I was just trying to spur discussion I wasn't trying to replace AES or
> something ... geez.
>
> Tom
------------------------------
From: newbie <[EMAIL PROTECTED]>
Subject: Re: A keen symmetric cipher idea
Date: Mon, 30 Apr 2001 12:49:55 -0300
Who is ignorant?
Tom St Denis wrote:
>
> "David Wagner" <[EMAIL PROTECTED]> wrote in message
> news:9cj24j$m4f$[EMAIL PROTECTED]...
> > Tom St Denis wrote:
> > >1. Both users pick two large primes p and q, then form N = pq
> > >2. To encode a message you take 0 < M < N and do, c1 = M mod p, c2 =
> > >M mod q
> >
> > This is utterly silly.
> >
> > p divides M - c1, so if you have two known plaintexts (M,(c1,c2)),
> > (M',(c1',c2')), then you can recover p as gcd(M - c1, M' - c1').
> >
> > You might want to study a bit more number theory before proposing any
> > more such ciphers.
>
> I agree. However my Koblitz book has not arrived and my "Dover Series"
> number theory books don't cover much of this type of math.
>
> I was just trying to spur discussion I wasn't trying to replace AES or
> something ... geez.
>
> Tom
------------------------------
From: Mok-Kong Shen <[EMAIL PROTECTED]>
Subject: Re: A Question Regarding Backdoors
Date: Mon, 30 Apr 2001 19:07:07 +0200
bob wrote:
>
> I am dabbling with my own flavor of an encrypted email client utilizing
> Rijndael 256-bit. I live in the States and am concerned about whether or
> not a backdoor is needed or mandated by the govt.
>
> Could someone please give me an informed reply? I get nervous easily and
> don't want my door being broken in by overzealous Bush-Troopers.
I am afraid that there is some logical inconsitency in the
above. IF you are in a situation where the government
requires you to implement a backdoor, THEN you are
almost surely required to implement it in such a way that
the government can break it with the special informations
that are needed to break it to be supplied by you to the
government prior to its approval of the marketing or
export of your product. A backdoor that it cannot profitably
exploit would mean no backdoor at all from the standpoint
of the government, isn't it? Or have I largely misunderstood
what you wrote above?
M. K. Shen
------------------------------
From: [EMAIL PROTECTED] (Bill Unruh)
Subject: Re: Censorship Threat at Information Hiding Workshop
Date: 30 Apr 2001 17:11:13 GMT
In <[EMAIL PROTECTED]> [EMAIL PROTECTED] (Leonard R. Budney)
writes:
][EMAIL PROTECTED] (Bill Unruh) writes:
]> ...copyright law, sets in...This monopoly is as artificial as any other
]> monopoly granted by the state. In this case the reason for this grant
]> of monopoly is to encourage production. There is no natural right to
]> a monopoly.
]However, copyright expresses the basic belief that an idea's originator
]is entitled to profit from his ideas. I think that's a good and fair
]principle--but when the cost of production (AND theft) falls to zero,
]all sorts of interesting complications arise.
Again, it is NOT theft. It deprives noone of any good. Do not try to
extend the definition of terms.
No, they do not express the basic belief that an idea's orginator is
entitled to profit. Copyright says nothing about ideas and offers ideas
no protection whatsoever. Furthermore, since the economic system of the
USA has as one of its tennents, the efficacy of competition, copyright
is an anomaly as it grants monopoly rights. Should Starbucks be granted
a monopoly in a city if they happen to be the first to set up a coffee
shop there? etc.
The theory behind copyright is that by granting a monopoly on copying
the specific EXPRESSION of something, one will encourage those arts.
However, that implies that the govt should be making the cost benefit
analysis to see if the monopoly right granted ( a right which prima
facia flies completely in the face of one of the philosophical
foundations of the economy-- competition) brings with it a commensurate
benefit. In software, I certainly do not believe it does. Even in books
I suspect it no longer does (How many poeple write books because their
great grandchildren may benefit from the copyright. Or rather in most
cases, their publishers, and not any issue of theirs.) Instead we get
large corporations demanding that the government keep them on their
gravy train by granting monopolies to them.
]> A creative work is not a thing. An embodiement can be, but it is not
]> embodyments copyight law controls, it is the act of copying.
]To you "emobodiment" means a "physical artifact". Your language is not
]consistent with copyright law. It's correct that *ideas* are not things;
]that's why copyright law protects a *specific form* given to an idea.
]> That act deprives noone of anything. He has as much of the item
]> afterwards as he did befor.
]It deprives him of the livelihood derivable from charging for use of his
]creative effort.
So does all economic activity. If I sell Joe a computer and you do not,
I am depriving you of the livelihood derivable from that sale. Should
computer sales be made into a monopoly?
Copyright also deprives society of the good of the wide dissemination of
that creative effort, a good which probably outweighs by far the
deprivation ( at least that is the attitude in all other fields of
economic endeavour.) Also if that is the reason, why limit copyrights?
Why are they not in perpetuity? After all Shakespear's descendents I am
sure would welcome the ability to impose copy and performance
restrictions on his plays. You have deprived them of a livelihood by
limiting the length of copyrights.
]> It is a public good to allow copying, just as it is believed
]> that the free market is also a public good.
]``Just as''? Copying may be a public good, but (supposing the existence
]of intellectual property) it is the opposite of a free market. You are
]taking away one man's means of livelihood, on the argument that somebody
]else needs it. That's socialism. (Just as extreme Stallmanism is really
]just software socialism.)
Hardly. I am not taking away anything from him. He has the right to sell
his copies in competition with others. I am solely depriving him of an
artificial monopoly right granted solely by the state, and not by any
"natural law". YOu deprive Starbucks of their livelyhood everytime you
open a competing coffee shop.
I do not propose taking away anything but an artificial right granted in
violation of one of the key tennants of western economics-- namely
competition.
]> The DMCA is similar to the types of law passed in the soviet union
]> preventing anyone but the state sanctioned companies from creating
]> tractors, TV sets, or coffee.
]With a vital difference. Soviet laws protected government monopoly. In
]the US, a temporary monopoly is up for anyone's grab: just be the first
]to think of something.
No, Soviet law also protected private monopoly. And it was also "up for
grabs" -- whoever had the political smarts to get appointed to run the
thing.
Note that 75 years is a use of the term "temporary" with which I had not
hithertofor been familiar. It is longer than the Soviet Union lasted.
Ie, it is longer than any monopoly granted by that government.
Once again, it is not "first to think of something". It is first to
express something in a particular way. Ie Copyright does NOT e
protect ideas, it protects a particular expression thereof. That is at
least one saving grace of it. (It is also another indication that the
theory behind copyright law is not what you imagine it to be).
------------------------------
From: [EMAIL PROTECTED] (Bill Unruh)
Subject: Re: RSA BRUTE FORCE
Date: 30 Apr 2001 17:14:26 GMT
In <[EMAIL PROTECTED]> [EMAIL PROTECTED] (Erictim) writes:
>THERE ARE SOME THINGS I DON'T UNDERSTAND ABOUT THE RSA ALGORITHM. MY
There are also things you do not understand about posting. Why should
anyone read a post all in capital letters?
------------------------------
Subject: Re: Censorship Threat at Information Hiding Workshop
From: [EMAIL PROTECTED] (Leonard R. Budney)
Date: 30 Apr 2001 13:52:52 -0400
[EMAIL PROTECTED] (Bill Unruh) writes:
> In <[EMAIL PROTECTED]> [EMAIL PROTECTED] (Leonard R. Budney)
>writes:
>
>] However, copyright expresses the basic belief that an idea's originator
>] is entitled to profit from his ideas. I think that's a good and fair
>] principle--but when the cost of production (AND theft) falls to zero,
>] all sorts of interesting complications arise.
>
> Again, it is NOT theft.
WHAT is not theft? I discussed no specific application of copyright law.
> It deprives noone of any good.
Practice making your pronouns refer to something specific, will you?
> Copyright says nothing about ideas and offers ideas no protection
> whatsoever.
True enough; I'm speaking English, not legalese. The premise behind
copyright law is that people are entitled to profit from their
*creativity*, where creativity is defined to be "a specific work
having some original content".
It was framed the way it was to address a specific problem: if I make a
buggy, and you take it, the economic damage is plain. But if I invent
something useful for mankind, and you steal my idea and become rich, the
harm is just as real--but much harder to precisely define.
> Furthermore, since the economic system of the USA has as one of its
> tennents...
You charge tenants rent. You live by tenets. There are no such things as
"tennents", although it might be a plausible old English construction
meaning "dwelling in a tent".
> ...the efficacy of competition, copyright is an anomaly as it grants
> monopoly rights.
You are mighty dismissive of some deep and interesting philosophical
issues. The fundamental issues are indeed interesting, AND deep. But
you even dismiss the most basic issues: If you make a suggestion to
your boss, and he passes it up the chain with his name on it, winning
promotions and accolades, then HE DONE YOU WRONG. Why, you ask? After
all, aren't ideas free? Doesn't knowledge belong to everyone? Do you
really "own" your suggestion?
> How many poeple write books because their great grandchildren may
> benefit from the copyright.
What an asinine question! The question is, "How many people would write
books if they had to work full-time jobs besides, because some snot-nosed
college kid keeps scanning it in and distributing millions of free
copies?"
>] It deprives him of the livelihood derivable from charging for use of his
>] creative effort.
>
> So does all economic activity. If I sell Joe a computer and you do not,
> I am depriving you of the livelihood derivable from that sale. Should
> computer sales be made into a monopoly?
You can't be that big an idiot. If I write a book, and you write a better
book, that's one thing. If I write a book, and you decide to give the
world a million free copies of my book, that's something else.
>] ``Just as''? Copying may be a public good, but (supposing the existence
>] of intellectual property) it is the opposite of a free market. You are
>] taking away one man's means of livelihood, on the argument that somebody
>] else needs it. That's socialism. (Just as extreme Stallmanism is really
>] just software socialism.)
>
> Hardly. I am not taking away anything from him. He has the right to sell
> his copies in competition with others.
Oh. You ARE that big an idiot. If I invent something really neato keen,
and you decide to make a fortune off my idea, then you haven't done
anything to me. I can only assume you are still in college (or live in
a socialist country).
There are difficult questions out there, but you keep denying
a fundamental principle. Ideas and creativity are not community
property. Protecting "ideas" is truly impossible, but protecting its
artifacts has served pretty well. Epsilon-cost duplication calls the
adequacy of those protections into question in several ways. But the
need for it cannot be denied.
Len.
--
The exceptional cases can be handled in other ways. Meanwhile,
software bloat costs RAM and disk space.
-- Dan Bernstein
------------------------------
From: [EMAIL PROTECTED] (David Wagner)
Subject: Re: A keen symmetric cipher idea
Date: 30 Apr 2001 17:55:50 GMT
Tom St Denis wrote:
>I was just trying to spur discussion I wasn't trying to replace AES or
>something ... geez.
"spur discussion"? To what end? If you want to learn about how to
design ciphers based on number theory, first you should learn about
number theory from the books before trying to learn from the newsgroup
-- that's a far more efficient use of everyone's time.
------------------------------
From: [EMAIL PROTECTED] (Erictim)
Date: 30 Apr 2001 17:57:00 GMT
Subject: Re: RSA BRUTE FORCE
thanks for the replys. i don't understand enough about programming languages
to code a program and test this. if you see this in a newsgroup you may need
to set your preferences to accept larger messages.
this is an example of the greater than,less than brute force attack i was
referring to. this would result in probably not more than 40000 test cases and
i have heard that computers are fast when doing multiplication. sorry about
caps
(0,0) (0,1) (0,2) (0,3) (0,4) (0,5) (0,6) (0,7) (0,8) (0,9)
(1,1) (1,2) (1,3) (1,4) (1,5) (1,6) (1,7) (1,8) (1,9)
(2,2) (2,3) (2,4) (2,5) (2,6) (2,7) (2,8) (2,9)
(3,3) (3,4) (3,5) (3,6) (3,7) (3,8) (3,9)
(4,4) (4,5) (4,6) (4,7) (4,8) (4,9)
(5,5) (5,6) (5,7) (5,8) (5,9) chart 1
(6,6) (6,7) (6,8) (6,9)
(7,7) (7,8) (7,9)
(8,8) (8,9)
(9,9)
(0,0)
(1,0)
(1,1)
(2,0) (2,1)
(2,2)
chart 2 (3,0) (3,1) (3,2) (3,3)
(4,0) (4,1) (4,2) (4,3) (4,4)
(5,0) (5,1) (5,2) (5,3) (5,4) (5,5)
(6,0) (6,1) (6,2) (6,3) (6,4) (6,5) (6,6)
(7,0) (7,1) (7,2) (7,3) (7,4) (7,5) (7,6) (7,7)
(8,0) (8,1) (8,2) (8,3) (8,4) (8,5) (8,6) (8,7) (8,8)
(9,0) (9,1) (9,2) (9,3) (9,4) (9,5) (9,6) (9,7) (9,8) (9,9)
a junction is considered to be the pair of numbers resulting in a value that
is immediately greater than and less than the number being compared to.
pairs are represented as (X, Y)
chart 1
find upper junction pair and do(X+1, Y-1)
if the lower pair of the junction is in the far left
column then take the upper junction pair and do(X+1, Y)
chart 2
find lower junction pair and do(X+1, Y+1)
if upper junction pair is in the far right column
then take the lower junction pair and do(X, Y+1)
example
X * Y = Z
X * Y = 39772916239307209103
5999999999 * 5999999999 = too small
5999999999 * 6999999999 = too large
(upper junction pair is (5,6))
(lower junction pair is (5,5))
by chart 1 take (5+1, 6) = (6,6)
6199999999 * 6399999999 = too small
6199999999 * 6499999999 = too large
(1+1, 4-1) = (2, 3)
6249999999 * 6359999999 = too small
6249999999 * 6269999999 = too large
(4+1, 6-1) = (5, 5)
6256999999 * 6355999999 = too small
6256999999 * 6356999999 = too large
(6+1, 5+1) = (7, 6)
6257399999 * 6356099999 = too small
6257399999 * 6356199999 = too large
(3+1, 1-1) = (4, 0)
6257489999 * 6356039999 = too small
6257489999 * 6356049999 = too large
(8+1, 3+1) = (9, 4)
6257492999 * 6356046999 = too small
6257492999 * 6356047999 = too large
(2+1, 7-1) = (3, 6)
6257493299 * 6356046099 = too small
6257493299 * 6356046199 = too large
(2+1, 0+1) = (3, 1)
6257493329 * 6356046109 = too small
6257493329 * 6356046119 = too large
(2+1, 0+1) = (3, 1)
last digit must be 1, 3, 7 or 9, test them all and
X = 6257493337
Y= 6356046119
6257493337 * 6356046119 = 39772916239307209103
example 2
X * Y = 239812014798221
19999999 * 09999999 = too small
19999999 * 19999999 = too large
(X, Y+1) = (1, 0+1) = (1,1)
14999999 * 14999999 = too small
14999999 * 15999999 = too large
(4+1, 5) = (5,5)
15399999 * 15499999 = too small
15399999 * 15599999 = too large
(3+1, 5-1) = (4,4)
15479999 * 15489999 = too small
15479999 * 15499999 = too large
(7+1, 9-1) = (8,8)
15484999 * 15485999 = too small
15484999 * 15486999 = too large
(4+1, 6-1) = (5,5)
15485799 * 15485899 = too small
15485799 * 15485999 = too large
(7+1, 9-1) = (8,8)
15485859 * 15485869 = too small
15485859 * 15485879 = too large
(5+1, 7+1) = (6,6)
last digit is 1, 3, 7 or 9
X=15485863
Y=15485867
15485863 * 15485867 = 239812014798221
------------------------------
From: Mike Rosing <[EMAIL PROTECTED]>
Subject: Re: DSA in GF(2^W)?
Date: Mon, 30 Apr 2001 12:56:15 -0500
Tom St Denis wrote:
> Is it possible to setup DSA for use in GF(2^W) instead of Z*p ?
>
> I.e
>
> let p be a 1024-bit irreducible polynomial
> let q be a a large factor of 2^1024 - 1
> let g be a generator such that g^((2^1024 - 1) / q) != 1
>
> What current attacks are there against GF(2^K) Discrete Log type
> problems? I will go look through my Eurocrypt collection.... any
> pointers would be nice :-)
The problem is that DLP over polynomials is easy. That's part of the reason
EC works, doing DLP over curves is hard. In plain GF(2^k) you have lots of
tools and lots of structure to work with, so DLP is simpler than GF(p). GF(p^n)
is simpler than GF(p) too, but when you get to larger p, it becomes hard due
to effort.
So look at it this way: you have log(p) bits, and finding DLP in GF(p) is hard.
suppose log base q(p) ~ 4. Then you'd have something like GF(q^4) (pure example
here ok!), and solving DLP in this would be much simpler than solving GF(p). When
you drop down to q=2, life becomes easy.
Patience, persistence, truth,
Dr. mike
------------------------------
** 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
******************************
