RE: PGP scripting...

From: Jason Coombs (jasonc@science.org)
Date: 01/11/03

  • Next message: John Viega: "Re: PGP scripting..." 
    From: "Jason Coombs" <jasonc@science.org>
To: "Kenneth Buchanan" <K.Buchanan@Kastenchase.com>, "'Tom Arseneault'" <TArseneault@counterpane.com>, "Chris Matthews" <chris@masc.ca>, "'Frank Knobbe'" <fknobbe@knobbeits.com>
Date: Fri, 10 Jan 2003 13:00:29 -1000

    Aloha,

    In addition to being confused about arbitrary asymmetry in RSA cryptography
    and whether or not e and n were reversibly derived from d such that
    possession of d was the same as possession of e and n, I was making a
    practical assertion that many RSA implementations aren't coded in such a way
    as to facilitate arbitrary designation of which key is public and which
    private.

    Microsoft .NET, for example, defines a private key as inclusive of its
    corresponding public key. A valid XML representation of a private key in the
    .NET Framework includes the public key. As in:

    rsaDecrypt.FromXmlString(
    "<RSAKeyValue><Modulus>vuQkEFfmNf/XTIRL/ga4WYBsA2GMq" +
    "IpUpwPmCEBWIQGwXfRioppWTdIWz01u6o4h8R38alnfbh7erO/O+anmgb" +
    "fHdCf+8oc5G0WcCU1AYp7hV5rBHQ4gb0oaIHi+RCKkcrvzQ2PZjchLcDf" +
    "N15SOgsXDf88fdxFzUoZA23RXrbs=</Modulus><Exponent>AQAB</Exp" +
    "onent><P>4LWIuM82AHAryV3ojQ6Uzef3L5VBpn3y1wRvffg3j27w/KyB" +
    "ou0Zo/LnqqBc885dfLqqaBEBewxLlEpoFfaIhw==</P><Q>2XkPOpd" +
    "Af6sbymL41pwNvZg2CXcc49DBYbamEW+I+xAFAvBSeMP6O09fqO0jN" +
    "mdFeTAbACrQl7gfMteeP9JiLQ==</Q><DP>XV/yBWHNfdceytlkBiF2" +
    "Ai4PEE3EbwvNOj4UmlLnu4mNSGHiqLI/wlnwnH1wwrsRLABhSUcvx1L" +
    "voRpeMCo2xw==</DP><DQ>rhbSERYphMoGGjK2fp44BbFGeLdIgjqHw" +
    "+AB+u0tW8XMLTkS3CgONdJpgoIq8Q8kt0nCI5UinIHBP+MJhI+3FQ==" +
    "</DQ><InverseQ>e9Bf8RurDeKstBP5Awmnc78WgBiaqVTVOpxx3YF" +
    "fsG+Q3YHK1PgRkQKp8uMIHafAIQ0cEq7BxotXd5PYoTN2VQ==" +
    "</InverseQ><D>iaZFgyt/K80y2VBE5AbAhHmgace8AATQCi" +
    "c7hxOth9uJ7BY/0fTs6uzl2dKCeszHGPGAhMgN34CPHbFHVKz5M64" +
    "QvimHE1imX3LPD7bWb00KMd+G0CKJ6BUcreeYpQffcFT3FwO3fEFY" +
    "g44j/2UGdU2RgMiUuvOT+DTO7Os+EtE=</D></RSAKeyValue>");

    The <Modulus> and <Exponent> represent the public key while the private key
    consists of <P>, <Q>, <DP>, <DQ>, <InverseQ>, and <D>.

    Based on the tests that I've done, Microsoft .NET doesn't allow you to load
    a private key into an instance of the RSA class and use it for encryption,
    you can only use it for decryption.

    As for encryption speed, encryption transformations with a public key
    (<Modulus> and <Exponent>) take far less time (approximately 1/15th as long)
    to complete as do decryption transformations with a private key (<P>, <Q>,
    <DP>, <DQ>, <InverseQ>, and <D>) under Microsoft .NET.

    Anyone know why? Is this a known performance differential with RSA or is
    Microsoft doing something strange?

    Sincerely,

    Jason Coombs
    jasonc@science.org

    -----Original Message-----
    From: Kenneth Buchanan [mailto:K.Buchanan@Kastenchase.com]
    Sent: Thursday, January 09, 2003 4:01 AM
    To: 'Tom Arseneault'; 'jasonc@science.org'; Chris Matthews; 'Frank
    Knobbe'
    Cc: secprog@securityfocus.com
    Subject: RE: PGP scripting...

    To be fair, it does depend on the cryptosystem you're using. Jason
    mentioned he wasn't clear on RSA, which indeed has a 'symmetry' between the
    keys that allows you to arbitrarily choose which is private and which is
    public.

    But his original post was correct if you are speaking of Discrete Log-based
    cryptosystems, as opposed to Factoring-based cryptosystems. ElGamal crypto
    is based on DLP. So is Elliptic Curve Cryptography, which is a variant of
    ElGamal. In these systems divulging your private key compromises the public
    key as well.

    ------------------------------------------------------------
    Kenneth Buchanan
    Software Developer
    Kasten Chase
    k.buchanan@kastenchase.com

    "You do not really understand anything unless you can explain it to your
    grandmother."
    -- Albert Einstein

    -----Original Message-----
    From: Tom Arseneault [mailto:TArseneault@counterpane.com]
    Sent: Wednesday, January 08, 2003 7:28 PM
    To: 'jasonc@science.org'; Chris Matthews; 'Frank Knobbe'
    Cc: secprog@securityfocus.com
    Subject: RE: PGP scripting...

    Not true, there is no relation between the keys in that way, you can't find
    one key from the other in any order. The only difference between the keys is
    that you keep the private key secret. Either key can be used to
    encrypt/decrypt messages. Here is an Algorithm for finding the public and
    private keys:

    Algorithm:
    Select two prime numbers p and q.
    Let n=p.q
    Let z=(p-1).(q-1)
    Choose a number d that does not divide z.
    Choose a number e such that is a multiple of z plus 1.

    e and n are published as the public key while d is kept secret as the
    private key.

    Example:
    p=3, q=11
    ->n=33, z=20
    Choose d=7
    Choose e=3, , i.e., z+1

    As you can see d and e have no relation to each other. If your private key
    is compromised but somehow they do not have e, since d has no relation to z
    (hence n) you can not determine e from d. Also although e has a relation to
    z (hence n) there is still no relation to either d so your still safe.

    Here is a quick over view of the public key encryption routines (the
    clearest I've yet seen) that explain the use of "n" in the above setup:
    Instead of sending plain text information P, transmitters compute the
    remainder C when Pe is divided by n. The receiver recovers the unencrypted
    message P by computing the remainder of Cd divided by n. ("P" stands for
    plain text, Pe is P modified by "e" (how exactly modified I don't recall)
    and Cd is C modified by "d", Pd and Ce should also be valid combinations)

    (The algorithm and example are taken off the web page
    "http://thalia.spec.gmu.edu/~pparis/classes/notes_101/node63.html")

    However since you normaly will freely publish your public key then it can be
    assumed that once someone gets ahold of your private key he/she will now
    have both your keys, just not for the reason you describe.

    As for the usage of the key in encryption and decryption, public key
    encryption is very compute intensive so while you could do bulk encryption
    with it whould be very slow.. The usual way things are done is that a
    symmetrical encryption will be used to encrypt a document (DES, 3DES,
    BLOWFISH, etc..., very fast) with a randomly generated key and that key is
    then encrypted with the public key of the person you sending the document
    to. Since only he, through the use of his private key, can decrypt the
    symmetrical key only he can decrypt the document.

    For a signature, you first take a hash of the document (MD5, SHA1, etc...)
    and then you encrypt it with your private key so that anyone with your
    public key can decrypt the signature and verify the document (since only
    you, thru the use of your private key, could have created the signature they
    can be assured that the document has not changed in transit and you were the
    one to send it)

    Tom Arseneault
    Security Engineer
    Counterpane Internet Security.
    "All humans are born Right-Handed...but the great ones overcome it."

    Relevant Pages

    • RE: PGP scripting...
      ... cryptosystems, ... In these systems divulging your private key compromises the public ... Here is a quick over view of the public key encryption routines (the ...
      (SecProg)
    • Re: RSACryptoServiceProvider decrypt with public key
      ... private key which my programs could decipher using a public key I've ... But since private key encryption and public key decryption isn't ... > If Alice gives Bob her public key, ...
      (microsoft.public.dotnet.security)
    • RE: PGP scripting...
      ... that you keep the private key secret. ... Here is a quick over view of the public key encryption routines (the ... Since only he, through the use of his private key, can decrypt the ...
      (SecProg)
    • Re: Separating public and private keys
      ... exchange - identifying yourself to the other party, ... a secure key for symmetric encryption for the session. ... public key, but it's slow, and you have to split messages into short chunks. ... >>Also, if you have the private key, you implicitly (if not ...
      (microsoft.public.platformsdk.security)
    • Re: rsa implementation question
      ... as there is no notion of blocks in public key ... |> cryptography, there's only the notion of doing an operation ... including RSA. ... and encryption, based on the "Exact Security" and "OAEP" papers ...
      (comp.lang.python)