Cryptography-Digest Digest #601, Volume #13 Thu, 1 Feb 01 01:13:01 EST
Contents:
Re: fast signing ("Matt Timmermans")
Re: A new cipher ("David Finch")
Re: A new cipher (David Wagner)
Re: Most secure code for US Citizen. (Eric Lee Green)
Re: A new cipher (Splaat23)
Re: More About Passwords (John Savard)
Re: Did NSA change the ECDSA-standard (Benjamin Goldberg)
Re: Integer sequence question (Benjamin Goldberg)
Re: Power mod operation optimization (rcg)
----------------------------------------------------------------------------
From: "Matt Timmermans" <[EMAIL PROTECTED]>
Subject: Re: fast signing
Date: Thu, 01 Feb 2001 03:17:43 GMT
It really sounds like you'll have a much easier time by tweaking the model a
bit.
For audit logs, it seems like something like this would be appropriate:
Sign every second, if more than 16 entries have accrued; and
Sign every hour, whether 16 entries have accrued or not.
If you _must_ ensure that you sign every 16 entries or so... well, you and I
know that no single PC web server is going to _sustain_ 10000 hits/sec over
long periods of time. Can you sign when the log is read, instead of while
it's being written, or can you delegate signing to a worker thread and force
a catch-up when the log is read?
Or perhaps you could be really clever and generate a signiture for any
portion of the log upon request, instead of signing every bit at the outset.
All these could be sold to your boss as offloading the signature work to the
log-reading phase, which is not performance-critical, from the writing
phase, which is.
------------------------------
From: "David Finch" <[EMAIL PROTECTED]>
Subject: Re: A new cipher
Date: Thu, 01 Feb 2001 03:29:37 GMT
Benjamin Goldberg <[EMAIL PROTECTED]> wrote in message
news:[EMAIL PROTECTED]...
> David Finch wrote:
> >
> > There seem to be a lot of bright people on this newsgroup. I recently
> > wrote a new encryption algorithm but I'm having trouble determining
> > it's strength with a fair level of certainty. It passes all of the
> > typical tests. A single bit change in either the key or the plaintext
> > results in a completely different ciphertext. The character
> > frequencies are about what you would get from random data. After I
> > first wrote it, I spent several days looking for and fixing all the
> > theoretical weaknesses I could find. I designed it to be simple to
> > understand, fast on 32bit processors, and secure enough that you
> > would probably need brute force to break it.
>
> Simply making the data look random isn't enough for security. I could
> XOR a file with output from rand(), and it would look random.
I know that.
>
> So far as I can see (and I might be mistaken), your algorithm is 100%
> linear, with no nonlinearity.
I think you must be mistaken.
Here is a summary of the steps it takes:
1) A 32bit hash is computed from the plaintext and placed in front of the
plaintext.
2) As an added precaution, a 2nd 64bit key is genetrated from the original
64bit key through a long and overly elaborate process. This 2nd key is
simply
xored with the plaintext.
3) The original 64bit key is then split into 2 32bit keys.
Here comes the real encryption:
4) The first 32bit key is used to encrypt from front to back. Each block is
affected by all of the previous blocks. The hash code at the beginning
serves
as an initialization vector. Not too different from many other proprietary
algorithms.
5) Finally, the 2nd 32bit key is used to reencrypt the data backwards. This
should hopefully destroy any possibly remaining patterns in the data, if
steps 1-5
haven't done this already.
It will take me a little while to describe it fully in english. Also I
apologize for not porting it to ansi C, commenting everything, or even
removing the old comments that are no longer apply to the code.
> I haven't bothered to look in more depth,
> but I'm sure that with some known plaintext, your key is easily
> recovered.
>
> > There are no random lookup tables used in the encryption, which should
> > make it easier to spot any major weaknesses.
>
> Lookup tables in most ciphers are not designed to be "random" they are
> designed to thwart linear and differential analysis.
I didn't mean to imply that they ALL were random.
>
> > You can specify multiple rounds, but hopefully 1 round will be enough.
> >
> > I need people who have free time and are willing to try to break it
> > without getting paid, since I'm in college and therefore have no
> > money.
>
> For a person to write a good cipher, they first have to know how to
> analyse ciphers. Have you ever broken [as practice] FEAL?
>
> Four round FEAL is insecure against both linear and differential
> analysis, and is easily breakable.
>
> If you don't know what differential analysis or linear analysis are, I
I've read about it, but I haven't actually attempted it yet. All I've
broken so far are the really simple ciphers that books always warn aren't
secure.
> would suggest you do some searches, visit your library, etc, and read up
> on them. After you've broken a few block ciphers [in reduced round
> versions, if they're supposedly secure ones], *then* introduce your
> cipher.
>
> Also, don't ever say that your cipher "is secure", say [for example]
I don't remember saying that.
> that it's secure against differential and linear analysis, and that a
> chosen plaintext/chosen ciphertext attack on a reduced round version
> works with X amount of work, and that using analysis method Z against
> the full round method requires more work than brute force.
>
> --
> Most scientific innovations do not begin with "Eureka!" They begin with
> "That's odd. I wonder why that happened?"
------------------------------
From: [EMAIL PROTECTED] (David Wagner)
Subject: Re: A new cipher
Date: 1 Feb 2001 03:38:24 GMT
Reply-To: [EMAIL PROTECTED] (David Wagner)
David Finch wrote:
>4) The first 32bit key is used to encrypt from front to back. Each block is
>affected by all of the previous blocks. [...]
>5) Finally, the 2nd 32bit key is used to reencrypt the data backwards. [...]
Have you looked at meet-in-the-middle attacks?
This sounds like a classic case of a danger zone where
square root attacks could apply, if you're not careful.
------------------------------
From: [EMAIL PROTECTED] (Eric Lee Green)
Subject: Re: Most secure code for US Citizen.
Reply-To: [EMAIL PROTECTED]
Date: Thu, 01 Feb 2001 04:23:08 GMT
On Wed, 31 Jan 2001 21:39:42 GMT, Douglas A. Gwyn <[EMAIL PROTECTED]> wrote:
>The problem with the original request is that it is missing
>information about threat environment and constraints, so it
>is impossible to be sure of any criteria one might come up
>with for the required level of "security", whatever that
>might mean. Better would be a simple statement of the
>actual requirements, as it is easier to be confident that a
>design has met specified requirements than to come up with
>a meaningful single measure of "security".
Absolutely.
Plus, the very fact that he's asking this question indicates that he
hasn't done his homework. He should at LEAST pick up a copy of
Applied Cryptography before even STARTING to think about "what's the
most secure code".
Most breaks come about because of poor systems design, not because of
poor ciphers. For example, I did the secure network layer for the BRU
Professional backup product. As far as I know the only vulnerability
in this is a theoretical man-in-the-middle attack during the initial
key exchange at backup client installation time. Once everything is
all nicely keyed up, all communication between the backup server and
backup clients is as secure as current state of the art can guarantee.
Sounds secure, right? Well one early beta tester noted that the backup
server left a configuration file world-readable that had a plain-text
database password in it, thus giving any user on that system the
ability to subvert the MySQL database that held the backup system user
table (and thus add himself into the backup program as a restore
superuser, thus allowing him to subvert the network). Whoops! The most
secure network layer in the world won't do anything if the password is
in plain sight for everybody to see! Needless to say, that problem is
now fixed, but the lesson is plain -- all the encryption in the world
will do no good if the rest of the system is insecure.
--
Eric Lee Green Linux Subversives
[EMAIL PROTECTED] http://www.badtux.org
------------------------------
From: Splaat23 <[EMAIL PROTECTED]>
Subject: Re: A new cipher
Date: Thu, 01 Feb 2001 04:15:21 GMT
I think Mr. Goldberg is right. I've taken a look at the basic
components forwardEncrypt and backwardEncrypt, which simply iterate
along the data ADD/XORing a changing key (data-dependent). It is a very
linear function. Most secure ciphers have some nonlinear function used,
whether it be S-boxes or data-dependent rotations. I could see some
serious differential attacks against this primitive. A chosen plaintext
attack would have a good chance of some strong differentials because
the keying data is only input twice in the whole algorithm: once in
forwardEncrypt and once in backwardEncrypt. In fact, break the hash and
you can get the key in just a few pairs.
Also, it is not even a block cipher, because ciphertext depends on ALL
bits of the plaintext. We could use his basic algorithm as a block, but
then I think all the security is gone because there is simply too
little keying material.
- Andrew
In article <[EMAIL PROTECTED]>,
"David Finch" <[EMAIL PROTECTED]> wrote:
>
> Benjamin Goldberg <[EMAIL PROTECTED]> wrote in message
> news:[EMAIL PROTECTED]...
> > David Finch wrote:
> > >
> > > There seem to be a lot of bright people on this newsgroup. I
recently
> > > wrote a new encryption algorithm but I'm having trouble
determining
> > > it's strength with a fair level of certainty. It passes all of the
> > > typical tests. A single bit change in either the key or the
plaintext
> > > results in a completely different ciphertext. The character
> > > frequencies are about what you would get from random data. After I
> > > first wrote it, I spent several days looking for and fixing all
the
> > > theoretical weaknesses I could find. I designed it to be simple to
> > > understand, fast on 32bit processors, and secure enough that you
> > > would probably need brute force to break it.
> >
> > Simply making the data look random isn't enough for security. I
could
> > XOR a file with output from rand(), and it would look random.
>
> I know that.
>
> >
> > So far as I can see (and I might be mistaken), your algorithm is
100%
> > linear, with no nonlinearity.
>
> I think you must be mistaken.
>
> Here is a summary of the steps it takes:
> 1) A 32bit hash is computed from the plaintext and placed in front of
the
> plaintext.
> 2) As an added precaution, a 2nd 64bit key is genetrated from the
original
> 64bit key through a long and overly elaborate process. This 2nd key is
> simply
> xored with the plaintext.
> 3) The original 64bit key is then split into 2 32bit keys.
> Here comes the real encryption:
> 4) The first 32bit key is used to encrypt from front to back. Each
block is
> affected by all of the previous blocks. The hash code at the beginning
> serves
> as an initialization vector. Not too different from many other
proprietary
> algorithms.
> 5) Finally, the 2nd 32bit key is used to reencrypt the data
backwards. This
> should hopefully destroy any possibly remaining patterns in the data,
if
> steps 1-5
> haven't done this already.
>
> It will take me a little while to describe it fully in english. Also I
> apologize for not porting it to ansi C, commenting everything, or even
> removing the old comments that are no longer apply to the code.
>
> > I haven't bothered to look in more depth,
> > but I'm sure that with some known plaintext, your key is easily
> > recovered.
> >
> > > There are no random lookup tables used in the encryption, which
should
> > > make it easier to spot any major weaknesses.
> >
> > Lookup tables in most ciphers are not designed to be "random" they
are
> > designed to thwart linear and differential analysis.
>
> I didn't mean to imply that they ALL were random.
>
> >
> > > You can specify multiple rounds, but hopefully 1 round will be
enough.
> > >
> > > I need people who have free time and are willing to try to break
it
> > > without getting paid, since I'm in college and therefore have no
> > > money.
> >
> > For a person to write a good cipher, they first have to know how to
> > analyse ciphers. Have you ever broken [as practice] FEAL?
> >
> > Four round FEAL is insecure against both linear and differential
> > analysis, and is easily breakable.
> >
> > If you don't know what differential analysis or linear analysis
are, I
>
> I've read about it, but I haven't actually attempted it yet. All
I've
> broken so far are the really simple ciphers that books always warn
aren't
> secure.
>
> > would suggest you do some searches, visit your library, etc, and
read up
> > on them. After you've broken a few block ciphers [in reduced round
> > versions, if they're supposedly secure ones], *then* introduce your
> > cipher.
> >
> > Also, don't ever say that your cipher "is secure", say [for example]
>
> I don't remember saying that.
>
> > that it's secure against differential and linear analysis, and that
a
> > chosen plaintext/chosen ciphertext attack on a reduced round version
> > works with X amount of work, and that using analysis method Z
against
> > the full round method requires more work than brute force.
> >
> > --
> > Most scientific innovations do not begin with "Eureka!" They begin
with
> > "That's odd. I wonder why that happened?"
>
>
Sent via Deja.com
http://www.deja.com/
------------------------------
From: [EMAIL PROTECTED] (John Savard)
Subject: Re: More About Passwords
Date: Thu, 01 Feb 2001 05:00:41 GMT
On Thu, 01 Feb 2001 01:38:27 +0000, David Hopwood
<[EMAIL PROTECTED]> wrote, in part:
>-----BEGIN PGP SIGNED MESSAGE-----
>
>John Savard wrote:
>> 6) Security computer
>...
>> - knows H(UPASS), ...
>
>This value is password-equivalent. Also, passwords should always be
>hashed with salt, to prevent precomputation attacks (where the same
>precomputed dictionary applies to all users) in the case that verifiers
>are compromised.
>Another, more serious problem is that the host doesn't appear to have
>any long-term secrets to authenticate it, so anyone can act as a
>man-in-the-middle host between the user and the security computer.
You are entirely correct, but those are *not* weaknesses in the
protocol. No one can act as a man-in-the-middle security computer
between the user and the host; *that* is what I intend to ensure.
The host has no long term secrets to authenticate it, because it is
assumed anything the host keeps on its hard drive can be stolen. The
host is what performs general services for the user; it is the
computer to which access is to be secured.
The security computer is kept under lock and key; its only function is
to help the host authenticate users; since it only responds to the
specific requests in the protocol, and its software is checked very
carefully for buffer overflows, etc., its hard drive - which indeed
contains password-equivalent values - is not open to attack.
The security computer is present to resolve problems like those in the
original version of PAK, where dictionary attacks were still possible.
So I went to lengths to ensure the verifier _on the host computer_ was
not password-equivalent. The intent is to create a strong protocol
between the user and the host computer.
The user doesn't need even to retain a permanent private key on his
own computer, which is an advantage.
Allowing the passwords to be salted will require only minor
modifications to the protocol, but salt doesn't make dictionary
attacks impossible in a time on the order of the password's entropy.
I've avoided weak steps (i.e., the security computer might
authenticate the host by its IP address) to focus on the real security
the protocol is intended to offer. (Stealing the password file on the
host computer is easy; copying the files of every single user to a
man-in-the-middle host might be difficult.)
In "Secure Passwords On The Cheap" I suggested giving the host
computer a long-term secret safely, based on the assumption its
computations are secure, but its hard disk is not, by stretching that
assumption to its limit: make root sign on each morning with a long
pass phrase with adequate entropy.
Essentially, I am relying on the safety of one specific computer - the
security computer - instead of just safety in numbers by distributing
information, as in Kaliski-Ford.
This sort of continues on from what I stated in an earlier post,
"Password Protocol: A Need to Cheat?"
<begin quote>
Looking at the goals of protocols like SRP and PAK, it seems to me
that to achieve them in full, it may be necessary to cheat by having a
computer, like the Kerberos server, which is itself secure, and whose
connection to the host computer is secure.
(There might be a clever way, based on generating random keys earlier
in the protocol, and allowing it to 'succeed' with a wrong password in
a way that is only dectectable as a failure if one knows the right
password, to achieve this without such a condition, but if so, _I_
haven't thought of it yet.)
Then, I can imagine that a protocol would be possible which achieves
the goal that dictionary attacks against the users' password are made
as difficult, for an attacker having the files on the computers at
both ends that are persistent between instances of the protocol, as
well as being able to mount active attacks on the communication line,
as EKE makes dictionary attacks for an eavesdropper with no access to
the password file.
So the setup is:
[User ---] User's computer --- Host computer [--- Security server]
and it is symmetric; the items in square brackets are assumed to be
physically secure. Thus, the attacker cannot read the user's mind to
obtain the user's password, or find it out by tapping the keyboard,
but the attacker may be able to read the user's hard disk. It's also
assumed neither the user's computer nor the host computer is corrupted
by a Trojan program, that the only compromise to their security that
is anticipated is the surreptitious reading of the contents of their
hard disks.
Not only is the setup symmetrical, but the protocol is symmetrical.
The user has a user ID of u, and knows a secret password p(u). The
security server stores a large random key q(u).
The user's computer stores E(A^x mod P,p), and the host computer
stores E(x,q) in the password file.
So the protocol begins like this: the user enters his ID and password
on his computer. The computer now figures out what A^x mod P, the
host's public key for the user, is; the user ID is sent to the host,
the host gets q, which unlike p is not brute-force searchable, from
the security server, and obtains x.
The user's computer generates a random number r, and can transmit
E(A^r mod P, H(A^x mod P)) to the host computer if necessary, or just
A^r mod P. (The extra complication follows a trick used in SRP and
PAK, but is it needed, or even relevant, here? And if it is needed,
even if it is used, will I have obtained the security I am aiming at?)
Both computers now know A^(xr) mod P, and thus a communications
session is set up by using that value as the key to exchange a session
key.
p, which is susceptible to a dictionary attack, is only used to
encrypt a public key.
A man-in-the-middle attack isn't possible, because the key pair x, A^x
is persistent.
The user's posession of the password p is verified, but only very
indirectly, by the user's ability to decipher A^x.
So the attacker is assumed to have E(A^x, p(u)) and E(x, q(u)). Only
the former can be attacked by a dictionary attack, but A^x looks like
a random binary number. (In other words, E(A^x, p(u)) has to be
handled using all the precautions required for EKE. Thus, what might
happen is that if P is 11xxx... then x is chosen so that A^x mod P is
of the form 10yyy... and E(yyy..., p(u)) is what is really stored.)
Even if the user's computer just transmits A^r mod P, an active
attacker can't substitute something for A^x, because that isn't
transmitted, it's on the user's computer.
Thus, it looks like a session key is established in a way that proves
the user's computer recieved p(u) and the host computer recieved q(u).
But this protocol could be used as the base on which to add other
steps that might be desired. Dangerous objects in other protocols
could be kept on the host computer's password file as long as they're
encrypted with q, even the user's password p itself, without violating
the specific security goal of the protocol.
Thus, an _elaborate_ protocol might work like this:
User: knows p(u).
User's computer: knows E(A^x, p(u)), E(y, QQ(u))
Host computer: knows E(x, q(u)), E(A^y, q(u)), E(QQ(u), q(u)),
E(E(QQ(u), p(u)), q(u))
Security server: knows q(u)
Step 1:
User gives p(u) to user's computer, and sends u along all the way to
the security server.
Step 2:
User's computer calculates A^x.
Step 3:
Security server gives q(u) to host computer.
Step 4:
Host computer calculates x, A^y, QQ(u), and E(QQ(u), p(u)) by using
q(u) as the key.
Step 5:
User's computer obtains a random number r, and calculates A^r.
Step 6:
User's computer transmits E(A^r, H(A^x)) to host computer.
Step 7:
Host computer, having x, obtains user's first temporary public key
A^r.
Using the now shared first session key, A^xr, E(E(QQ(u), p(u)),
H(A^xr)) is transmitted to the user's computer.
Step 8:
User's computer uses QQ(u) to obtain its private key, y, which, being
a private key, is guarded by QQ(u) rather than the weak p(u).
Step 9:
User's computer obtains a random number s, and calculates A^s, and
transmits E(A^s, H(A^xr)) to the host computer.
Step 10:
Host's computer obtains a random number t, and calculates A^t, and
transmits E(A^t, H(A^xr)) to the user's computer.
Step 11:
Both computers calculate their new shared session key, which is H(A^xs
+ A^yt) where + can be addition modulo P, XOR, or concatenation.
This uses elements of Kerberos (the security server), but mainly it
makes use of EKE to carry out a version of KEA. It relies on EKE as
presented here, although perhaps it can be modified to work with other
techniques.
By transmitting E(QQ(u), p(u)) to the user's computer, a stronger
authentication of p is obtained, because p is now used to work on
something kept on the host side. But it's still a fixed item; one
could do a more conventional challenge-response by storing, say,
E(H(p(u)), q(u)) on the host computer, and then the host computer
thinks of a random challenge z, transmits E(z, H(A^xs + A^yt)) and the
user replies with E(E(z, H(p(u))), H(A^xs + A^yt)) ... the exchange
being encrypted, a dictionary attack to find the password is again
forestalled, but if the encryption is securely authenticated at this
point, further authentication doesn't add to the security.
<end quote>
In a thread entitled "SRP - not good enough?", I began with
<begin quote>
In SRP, the host computer stores the values s and v, where v is a
public key, derived from a private key calculated from a hash of s and
the user's password.
This means that a dictionary attack can be mounted on the password
file, since for each password tried, one just performs two direct
computations: hash s and P, then calculate a public key from a private
key.
One does *not* have to crack a public key problem for every password
tried.
The dictionary attack is somewhat more expensive, because a public-key
computation is slower than a conventional encryption or a hash
function, but not extraordinarily so.
<end quote>
and then
<begin quote>
Finding information on PAK, I see that PAK-X protects the server's
password file from dictionary attack, but a dictionary attack is still
possible if the user's computer files are obtained.
And Augmented EKE doesn't protect against dictionary attack.
<end quote>
so if there's a new protocol that *really* protects against dictionary
attack out there, I haven't encountered it. That's why I'm showing how
one can obtain such protection - if one has one computer dedicated to
a security function which can be considered immune to attack.
John Savard
http://home.ecn.ab.ca/~jsavard/crypto.htm
------------------------------
From: Benjamin Goldberg <[EMAIL PROTECTED]>
Subject: Re: Did NSA change the ECDSA-standard
Date: Thu, 01 Feb 2001 05:18:27 GMT
Roger Schlafly wrote:
>
> DJohn37050 wrote:
> > I am the editor of X9.62 ECDSA and here is what I observed:
> > 1) Just before ECDSA was being balloted, there were concerns that
> > curves over 2**m, m composite might be weaker than over 2**p, p
> > prime. As nothing was known, they were allowed, after a lot of
> > discussion. Because of the compositeness, some argued that they
> > were faster; Certicom argued that they were riskier, but lost that
> > discussion as there was no proof.
> > 2) Then NIST published their recommended curves, none of them were
> > so-called composite binary curves. There were all over prime fields
> > or "prime" binary fields. By agreement, NIST can use NSA for
> > cryptographic consultation, as they did with AES also. ...
>
> I guess the conspiracy theorists might conclude that those are the
> curves that NSA can break.
Only if those conspiracy theorists were very stupid and completely
ignored point number 4 -- which was that it was later proved that
non-prime fields were weak.
Now, if NSA has suggested that fields over 2**m, m composite, were
better, THEN the conspiracy theorists might have something to point to.
--
Most scientific innovations do not begin with "Eureka!" They begin with
"That's odd. I wonder why that happened?"
------------------------------
From: Benjamin Goldberg <[EMAIL PROTECTED]>
Subject: Re: Integer sequence question
Date: Thu, 01 Feb 2001 05:24:06 GMT
Ned Scholes wrote:
>
> The integer sequence
> 1, 2, 6, 18, 54, 162, 486, 1458, 4374, 13122, 39366, 118098, 354294,
> 1062882, 3188646...
>
> has the following equation:
>
> 2*3^(n-1), n >= 1.
>
> I would like to have on the same form as i.e the fibonacci sequence
> (fib(n) = fib(n-1) + fib(n-2)).
>
> Is it possible to convert this expression on that form? With the
> condition that t(1) = 1.
To the best of my knowledge, there is no non-recursive formula which
describes the fibonacci sequence. There is one that comes close (it
involves the cieling function, and a power of euler's number), but by
the "law of small numbers," it is wrong, and only works up to a point.
--
Most scientific innovations do not begin with "Eureka!" They begin with
"That's odd. I wonder why that happened?"
------------------------------
From: [EMAIL PROTECTED] (rcg)
Subject: Re: Power mod operation optimization
Date: Thu, 01 Feb 2001 05:33:28 GMT
I can't make any sense of your vb code. Here is an example of how to
do it in Java:
/*
Function ModExp performs modular exponentiation to calculate
a^x mod b.
Rather than a simple loop, the algorithm uses repeated squarings to
improve efficiency when the exponent is large.
References:
1. Elementary Number Theory by Eynden, pg 140.
2. Algorithms by Cormen, Lieserson & Rivest, pg 829.
Note that the loop body executes log2(x) times.
This algorithm is very efficient for large exponents. A simple loop
might be more efficent for smaller exponenets. I have not analyzed
how large an exponent makes this the more efficient choice.
*/
static int modExp(int a, int x, int b) {
int r=1;
while (x>0) {
if (x % 2 != 0)
r = (r*a) % b;
a = (a*a) % b;
x = x / 2;
}
return r;
}
And a version in Pascal:
function ModExp(a, x, b : LongInt) : LongInt;
var
r : LongInt;
begin
r := 1;
while x > 0 do begin
if x mod 2 <> 0 then
r := (r*a) mod b;
a := (a*a) mod b;
x := x div 2;
end;
ModExp := r;
end;
Hope this helps. Good luck,
Bob.
On Tue, 30 Jan 2001 02:47:59 GMT, "Adam Smith" <[EMAIL PROTECTED]>
wrote:
>Well, I finally got some keys donated to me : )
>
>I plugged them in and notice that it takes an extended amount of time to
>generate a signature or verify it (for those of you who have read my
>previous posts, surprise surprise!)...
>
>All of the things taking up the time is my power mod function ( (x ^ y) mod
>z) ). Here's the code I have as of now (for those of you who don't know VB,
>it's pretty easy to catch on):
>
>
>
>
>BEING CODE
>-------------------
>
>'outp = (s1 ^ s2) mod s3
>
>Public Sub bModPower(s1 As String, s2 As String, s3 As String, Outp As
>String)
>(NOTE: First part is just notes (starts with a '))
> 'Use variation of "Russian Peasant Metho
> ' d" to figure m=(c^d) mod n.
> 'Byte, Jan 83, p.206.
> 'test value: (71611947 ^ 63196467) mod 9
> ' 4815109 = 776582
> 'm=1
> 'do
> ' if d is odd then m=(m*c) mod n
> ' c=(c*c) mod n
> ' d=int(d/2)
> 'loop while d>0
> 'm is the answer
> 'remember modulus for next call
> Dim c As String, d As String
> Static n As String
> 'positive numbers only, modulus must be
> ' >1! Find mod inverse if s2=-1.
> Outp = err
> If Len(s3) Then n = s3
> If bIsNeg(s1) Or bIsNeg(n) Then Exit Sub
>
>
> If bIsNeg(s2) Then
> If bIsEqual(s2, "-1") Then bModInv s1, n, Outp
> Exit Sub
> End If
> c = s1
> d = s2
> Outp = one
>
>
> Do
> If bIsOdd(d) Then bMul (Outp), c, Outp: bMod (Outp), n, Outp
> bMul (c), (c), c
> bMod (c), n, c
> bDivInt (d), two, d
> Loop Until bIsZero(d)
>End Sub
>
>END CODE
>
>
>NOTES: Most of the functions whose code is not included are pretty self
>explanitory (i.e. bIsNeg & bMul). However, the format is more-or-less odd
>(hey, I didn't code it! : ) ... for most of the functions, instead of
>naming them as functions they're Subs, and it returns its result in the last
>argument you pass it (for example for this you pass four variables: s1, s2,
>s3, and outp. Outp is where you get the results from)...All of the code
>executes very quickly until you get to the Do loop. then the time it takes
>for each loop seems to increase.
>
>Any thoughts?
>
>Thanks once again,
>Adam Smith
>
>
------------------------------
** 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
******************************
