Cryptography-Digest Digest #294, Volume #13 Fri, 8 Dec 00 18:13:00 EST
Contents:
Re: breaking rsa knowing the original text (Bryan Olson)
Re: Modular arithmetic ("Michael Scott")
Re: [globera announcement 1] "Efficient Descriptive Data Format" (Mok-Kong Shen)
Re: Modular arithmetic ("Barron Hulver")
BeeCrypt ElGamal (shren)
Re: Modular arithmetic ("Bruce Murray")
Re: document signing, XML canonicalization and why EDDF is a better (Roger Schlafly)
Re: Fips Pub 140-1 and RNG (Tim Tyler)
Re: How to embed a key in executable code? (Darren New)
ASM code public/private key cryptography source code ("James Dorrington")
Re: breaking rsa knowing the original text (Bill Unruh)
Re: document signing, XML canonicalization and why EDDF is a better choice (denis
bider)
Re: breaking rsa knowing the original text (Bill Unruh)
Re: [globera announcement 1] "Efficient Descriptive Data Format" preliminary
specification and SDK released (denis bider)
Re: weten we die PIN? (John)
----------------------------------------------------------------------------
From: Bryan Olson <[EMAIL PROTECTED]>
Subject: Re: breaking rsa knowing the original text
Date: Fri, 08 Dec 2000 20:58:24 GMT
Simon Johnson wrote:
> Yeah, one must remember that in SOME public key algorithms (the
> knapsack algorithms for example) that the public and private cannot be
> swaped around without destroying the security of the system. Since the
> original post involved RSA, this isn't a problem.
Using RSA they usually cannot be swapped. Most key generators
choose a specific e and compute d from that (and the factors
of course).
More to the point for this question, public key systems by
definition allow known message attacks. If the algorithm
supports encryption the attacker can encrypt his own messages
with it, regardless of how key usage bits are set. Even if an
algorithm is sign-only, the verifier still gets the signature
and the message.
--Bryan
Sent via Deja.com http://www.deja.com/
Before you buy.
------------------------------
From: "Michael Scott" <[EMAIL PROTECTED]>
Subject: Re: Modular arithmetic
Date: Fri, 8 Dec 2000 21:13:44 -0000
"Simon Johnson" <[EMAIL PROTECTED]> wrote in message
news:90raa6$uck$[EMAIL PROTECTED]...
> Since 65537 is prime. Then the inverse of any number, n, can be
> computed as follows:
>
> n^65536 mod 65537
>
Not quite. Its n^65535 mod 65537. In the exponent you work mod phi(p) where
phi(p) is the Euler totient function - not mod p. In this case since p is
prime, phi(p) is p-1, and so "-1" in the exponent is p-2. So n^65535 mod
65537 is the same as n^(-1) mod 65537 which is exactly what you want. As you
say its not the quickest way - that's the extended GCD algorithm.
Mike Scott
> There are more sleak ways, but that's the easiest (and the shortest) to
> write here :)
>
> Simon
> --
> Hi, i'm the signuture virus,
> help me spread by copying me into Signiture File
>
>
> Sent via Deja.com http://www.deja.com/
> Before you buy.
------------------------------
From: Mok-Kong Shen <[EMAIL PROTECTED]>
Subject: Re: [globera announcement 1] "Efficient Descriptive Data Format"
Date: Fri, 08 Dec 2000 22:29:46 +0100
denis bider wrote:
>
> Mok-Kong Shen<[EMAIL PROTECTED]> wrote:
> >So I guess one should be able to use your format to code
> >some data inside an XML document. Would that work? Thanks.
>
> At least two techniques could be used to embed EDDF data within XML:
> - Since EDDF and XML are very similar in structure, the EDDF
> document can be translated to XML via a simple set of translation
> rules. It would not be very difficult to develop and standardize a
> universal set of translation rules for conversions like this.
> - On the other hand, if the ability to access EDDF-encoded
> information from an XML program is not important, the EDDF document
> can simply be converted to Base64 and dumped into the XML document as
> text.
>
> The preferred translation, however, is the other way around: XML to
> EDDF. EDDF is generally what you will prefer to use for a digital
> signature, and XML is what the original data format would be. Again,
> this is a straightforward translation process. Using a proper set of
> rules (a set that is significantly less complex than the set of rules
> required for XML canonicalization), the XML document will be
> implicitly converted to a canonical form that is suitable for digital
> signing.
Elsewhere I saw the phrase 'XER, or XML Encoding Rules (for ASN)'.
I don't know what that is. Does that say something to you?
M. K. Shen
------------------------------
From: "Barron Hulver" <[EMAIL PROTECTED]>
Subject: Re: Modular arithmetic
Date: Fri, 8 Dec 2000 16:36:16 -0500
"Simon Johnson" <[EMAIL PROTECTED]> wrote in message
news:90raa6$uck$[EMAIL PROTECTED]...
> In article <90otoo$1js8$[EMAIL PROTECTED]>,
> "KENNETH H MARTIN" <[EMAIL PROTECTED]> wrote:
> > Please forgive my ignorance, but to decrypt an IDEA cipher
> > I need to find the multiplicative inverse of a 16-bit number,
> > Mod 66537. What if there are no inverses less than the
> > modulus, say for a relatively prime number like 5? Is there
> > a trick to this?
> >
> >
> Since 65537 is prime. Then the inverse of any number, n, can be
> computed as follows:
>
> n^65536 mod 65537
>
> There are more sleak ways, but that's the easiest (and the shortest) to
> write here :)
>
> Simon
> --
> Hi, i'm the signuture virus,
> help me spread by copying me into Signiture File
>
>
> Sent via Deja.com http://www.deja.com/
> Before you buy.
I dont' see it. Would you elaborate on how this can be used to calculate an inverse?
n^(p-1) mod p is always a 1 for any n not a multiple of p by Fermat's Theorem.
To calculate the inverse, use the Extended Euclidean algorithm.
The original poster said he is looking for the inverse of a number n mod a prime.
This can be written as:
n*x === 1 (mod p)
n times x is congruent to 1 mod p
(where x is best thought of as n^(-1) and not as 1/n).
Taking very small steps, rewrite the equation as follows:
n*x - 1 === 0 (mod p)
This means n*x - 1 is divisible by p
which means the n*x - 1 is a multiple of p
Therefore
n*x - 1 = p*y
n*x + p*y = 1
Now solve using the Extended Euclidean Algorithm.
For example, letting n = 3 and p = 65537, the equation is
3x + 65537y = 1
and solving you get
gcd=1, x=21846, y=-1.
Plugging back in to verify you find
3*21846 + 65537(-1) = 1
Therefore the inverse of 3 (mod 65537) is 21846
Barron
------------------------------
From: shren <[EMAIL PROTECTED]>
Subject: BeeCrypt ElGamal
Date: Fri, 08 Dec 2000 21:35:31 GMT
I'm trying to do some work with BeeCrypt's ElGamal algorithm,
but I'm having a few difficulties. In elgamal.h, there are
signing algorithms:
elgv1sign
elgv3sign
and verification algorithms:
elgv1vrfy
elgv3vrfy
How, however, does one generate the keys? There's no obvious routine
to use, or any hints as to how this should be done.
Also the variable names in the sign and vrfy are a little unclear,
but I think I can work that out . . . once I know how to generate the
key.
Is BeeCrypt a library in good standing? Does anyone care to suggest
a different public signature algorithm library in good standing?
------------------------------
From: "Bruce Murray" <[EMAIL PROTECTED]>
Subject: Re: Modular arithmetic
Date: Fri, 8 Dec 2000 21:31:42 -0000
I think that should be n^65535.
a^(p-1) = 1 mod p and a^(p-2) = a^(-1) mod p
Bruce
"Simon Johnson" <[EMAIL PROTECTED]> wrote in message
news:90raa6$uck$[EMAIL PROTECTED]...
> In article <90otoo$1js8$[EMAIL PROTECTED]>,
> "KENNETH H MARTIN" <[EMAIL PROTECTED]> wrote:
> > Please forgive my ignorance, but to decrypt an IDEA cipher
> > I need to find the multiplicative inverse of a 16-bit number,
> > Mod 66537. What if there are no inverses less than the
> > modulus, say for a relatively prime number like 5? Is there
> > a trick to this?
> >
> >
> Since 65537 is prime. Then the inverse of any number, n, can be
> computed as follows:
>
> n^65536 mod 65537
>
> There are more sleak ways, but that's the easiest (and the shortest) to
> write here :)
>
> Simon
> --
> Hi, i'm the signuture virus,
> help me spread by copying me into Signiture File
>
>
> Sent via Deja.com http://www.deja.com/
> Before you buy.
------------------------------
From: Roger Schlafly <[EMAIL PROTECTED]>
Subject: Re: document signing, XML canonicalization and why EDDF is a better
Date: Fri, 08 Dec 2000 14:01:36 -0800
denis bider wrote:
> EDDF, on the other hand, tries to make things straightforward for the
> interpreter. A well-formed EDDF document can only be one that could
> not have been presented in any other form. Signatures are therefore
> very easy to verify - you take the document as it is, and you verify
> the signature. If it is valid, it is valid, if it is not, it is not.
>
> Once again, I recommend that you visit [http://www.eddf.org] and
> download the specification. There is a "Motivation" section that
> explains much of the same things I have explained in this message.
The main advantage of EDDF seems to be that it uses ASN.1 DER
instead of XML. This seems like a step backwards to me. Who
wants to sign an ASN.1 document?
------------------------------
From: Tim Tyler <[EMAIL PROTECTED]>
Subject: Re: Fips Pub 140-1 and RNG
Reply-To: [EMAIL PROTECTED]
Date: Fri, 8 Dec 2000 22:06:58 GMT
[EMAIL PROTECTED] wrote:
:> Random numbers are often required for "Power On Self-Test"s (POSTs).
:> Could that have been what the document was talking about?
: It was indeed. What difference does it make whether these tests are
: executed on power up as opposed to being executed at any other time ?
If damage is most likey to occur while switched off, or while being
switched on and off, a POST catches the problem as soon as possible.
Sometimes it is possible to automatically route around problems.
--
__________ http://alife.co.uk/ http://mandala.co.uk/
|im |yler [EMAIL PROTECTED] http://hex.org.uk/ http://atoms.org.uk/
------------------------------
From: Darren New <[EMAIL PROTECTED]>
Subject: Re: How to embed a key in executable code?
Date: Fri, 08 Dec 2000 22:17:41 GMT
[EMAIL PROTECTED] wrote:
> stand by my statement, it's impossible to prevent the piracy of
> software (or any data) through anything related to crypto.
It seems that such a situation might be reducable to the halting problem?
Something along the lines of "given any program without key K in the input
to the program, can it halt?" Replace "halt" with "get past the check for
valid key" (i.e., the output equivalent of the halting problem) and someone
better at such stuff than I might be able to prove it one way or another.
Basically, some folks here are asserting that it's impossible to make an
algorithm so hard to understand that one cannot figure out if it ever gets
to a certain statement or not. I would contend that the halting problem
would seem to imply that's wrong. (Of course, AFAIK the halting problem only
applies to unbounded computers, etc, but still...) To say "it's impossible"
rather than "nobody knows how" or "it's extremely difficult" is a
simplification, methinks.
--
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.
------------------------------
From: "James Dorrington" <[EMAIL PROTECTED]>
Crossposted-To: comp.lang.asm.x86
Subject: ASM code public/private key cryptography source code
Date: Fri, 08 Dec 2000 22:27:19 -0000
Does anyone have (or could direct me to) some source code for public and
private key cryptography? Assembly source code prefered (x86.)
thx in advance
------------------------------
From: [EMAIL PROTECTED] (Bill Unruh)
Subject: Re: breaking rsa knowing the original text
Date: 8 Dec 2000 22:39:53 GMT
In <90p364$77i$[EMAIL PROTECTED]> [EMAIL PROTECTED] writes:
>Hi, I'm trying to figure out if it is much simpler to
>break RSA knowing the original text and the encrypted text.
>I mean, if some knows the original and the encrypted data
>how easy will be to get the key ??
Since anyone in the world can generate as many encrypted-plaintext pairs
as they want, all estimates of RSA strength assume that the attacker has
an unlimited supply of such pairs. As far as is known the only want to
break RSA is to factor the modulus. There may be some other way, but
"nobody" knows it.
------------------------------
From: [EMAIL PROTECTED] (denis bider)
Subject: Re: document signing, XML canonicalization and why EDDF is a better choice
Date: Fri, 08 Dec 2000 22:43:28 GMT
On Fri, 08 Dec 2000 14:01:36 -0800, Roger Schlafly
<[EMAIL PROTECTED]> wrote:
>denis bider wrote:
>> EDDF, on the other hand, tries to make things straightforward for the
>> interpreter. A well-formed EDDF document can only be one that could
>> not have been presented in any other form. Signatures are therefore
>> very easy to verify - you take the document as it is, and you verify
>> the signature. If it is valid, it is valid, if it is not, it is not.
>
>The main advantage of EDDF seems to be that it uses ASN.1 DER
>instead of XML. This seems like a step backwards to me. Who
>wants to sign an ASN.1 document?
Roger,
thank you for this comment. This might be a common misconception, and
it is something that I would like to clarify.
First of all, the strength of EDDF is not inherent in its use of DER.
Indeed, it is certainly possible to design a data format that would
use DER and retain all the weaknesses of XML. What makes EDDF stronger
is not the use of DER on its own, but rather that the format is
designed entirely with document canonicality in mind. Every step in
the creation of an EDDF document must be compatible with the basic
premise that the document's ultimate form should be the only possible
form. This could have been done on a textual basis just as well - the
fact that it would be text-based would just make the rules more
difficult to verbalize and implement.
DER was, therefore, a matter of my personal choice.
I do not know whether the general public regards ASN.1 as a thing of
the past - especially when compared to a newer technology like XML.
Nevertheless, I think that such an opinion would be a fairly
superficial one, and would be a likely candidate for reversal after
the XML hype is over.
The reasons behind a judgement that DER is "backwards" would probably
have something to do with the fact that XML can be read in a text
editor; and DER cannot. And that XML can be created with a text
editor; while DER cannot.
The fact is, XML is just as impractical for human inspection as DER. I
have had the privilege of working with XML in a real life environment.
In such an environment, the majority of XML documents that you meet
are computer-generated. These XMLs are usually all stuffed in a single
line, no formatting involved, and this is rightly so; such documents
are more compact, easier to generate and easier to process. However,
they are also very difficult to navigate by hand. What you need to
work with these XML documents is... A VIEWER.
Having said that, my premise should be obvious. You NEED a viewer to
work with any kind of XML that is not constrained to laboratory
conditions. But then, if we need a viewer most of the time anyway, why
are we using this text-based format in the first place? The sole fact
that it is text-based provides us with a million of difficulties, and
at the bottom line - little real advantages. The overall balance, I
dear say, is negative.
The advantage of using a text-based format is illusionary. You have
all these difficulties with it, and then you need a viewer anyway. Why
not just use a format that drags less baggage along?
I think that this answers the point of document read-ability. As for
document write-ability: you can use a text editor to write EDDF just
as well. Just write up an XML and run xml2eddf. As for the future, I
anticipate easy to use GUI programs in which it will be possible to
manually produce EDDF (or XML) documents in a manner that will be much
more practical than today's hand-crafting of XMLs. If you've tried it,
you know it could be made much more comfortable than it is.
So there you have it. :-)
Kind regards,
denis
------------------------------
From: [EMAIL PROTECTED] (Bill Unruh)
Subject: Re: breaking rsa knowing the original text
Date: 8 Dec 2000 22:43:40 GMT
In <90r8gb$sql$[EMAIL PROTECTED]> Simon Johnson <[EMAIL PROTECTED]> writes:
]>
]> A nit: it's the same *type* of public key. Sometimes
]> two different actual keys are used. (I agree with the
]> essential point: that the vulnerability is no different.)
]>
]> JM
]>
]Yeah, one must remember that in SOME public key algorithms (the
]knapsack algorithms for example) that the public and private cannot be
]swaped around without destroying the security of the system. Since the
]original post involved RSA, this isn't a problem.
Another nit-- in most implimentations, exchanging the public and private
RSA keys would make RSA totally useless, since the public exponent is
usually chosen to be of the form 2^x+1 for some very small x
Making that your private exponent would be disasterous. IF you chose the
public exponent randomly, then the two would be completely symmetric I
think is what you wanted to say.
------------------------------
From: [EMAIL PROTECTED] (denis bider)
Subject: Re: [globera announcement 1] "Efficient Descriptive Data Format" preliminary
specification and SDK released
Date: Fri, 08 Dec 2000 22:49:29 GMT
On Fri, 08 Dec 2000 22:29:46 +0100, Mok-Kong Shen
<[EMAIL PROTECTED]> wrote:
>> The preferred translation, however, is the other way around: XML to
>> EDDF. EDDF is generally what you will prefer to use for a digital
>> signature, and XML is what the original data format would be. Again,
>
>Elsewhere I saw the phrase 'XER, or XML Encoding Rules (for ASN)'.
>I don't know what that is. Does that say something to you?
>
Well, let me put it this way. XER is a good way to convert data from a
good format to a much worse format, and back.
What XER does is that it takes an ASN.1 document and it bloats it into
XML by literally copying all information that appeared in the original
ASN.1 document. This XML can then be parsed to retrieve the same ASN.1
document, which can then again be expressed with any of the other
ASN.1 encoding rules, such as DER.
Basically, XER is a kludge that makes it possible to transfer ASN.1
documents through XML.
Kind regards,
denis
------------------------------
From: John <[EMAIL PROTECTED]>
Crossposted-To:
alt.cracks.nl,alt.nl.telebankieren,nl.comp.crypt,nl.financieel.bankieren,nl.juridisch
Subject: Re: weten we die PIN?
Date: 8 Dec 2000 23:06:50 GMT
Olaf Biemond wrote:
<knip>
> > Veilig zou ik dat ook niet willen noemen. Mits je de lijn kunt vinden
> > tussen de automaat en de PTT kast kun je de lijn met een simpel thuis
> > te bouwen apparaatje aftappen.
>
> En dan kun je er vervolgens: helemaals niets mee. De data is zwaar
> ge-encrypt met regelmatig wisselende sleutels. Ik zou het echt wel
> veilig willen noemen. Misschien zelfs wel een beetje overdone.
Hmm, overdone? Lijkt me niet, lees het volgende artikel maar eens.
http://www.info-sec.com/crypto/99/crypto_060899c_j.shtml
Gr, John
------------------------------
** 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 (and sci.crypt) via:
Internet: [EMAIL PROTECTED]
End of Cryptography-Digest Digest
******************************
