Results 1 to 9 of 9

Thread: Cryptic Formula Help

  1. #1
    Opti
    Guest

    Question Cryptic Formula Help

    Hi All,

    I Was Hoping To Get Some Help Understanding This Formula More

    x = a ^ b MOD c

    Whereas :-

    a = Variable
    b = Variable
    c = Constant
    x = Constant

    All Integers (Of Course)

    After Further Analysis I Found

    a = Product Of 2 Primes
    b = Product Of 2 Primes
    c = NOT A Product Of 2 Primes

    So

    x = p1*p2 ^ p3*p4 MOD c


    So I Gather From This, The Method Is Not RSA Encryption As c Cannot Be
    Broken Into 2 Primes. I Have Searched Around The Net For Information
    But Im At A Loss To Understand It More, I Was Hoping Someone Here
    Maybe Knows The Method So I Could Search For Some Info / Source On
    The Web Or Could Explain How To Calculate a & b Or Maybe If Possible
    To Change Sides Of The Equation

    With My Basic Algebra Skills I Can See

    a ^ b Must Be x Plus A Multiple Of c


    Any Help Would Be Great


    On My Travels Looking For Information I Found An Interesting Site About
    Number Theory And RSA with Examples For MathLab, Hope The Link Helps
    Someone Else

    h**p://w*w.ma.umist.ac.uk/rb/teaching/117/
    I promise that I have read the FAQ and tried to use the Search to answer my question.

  2. #2
    הבּרוּ נשׂאי כּלי יהוה mike's Avatar
    Join Date
    Mar 2001
    Posts
    491
    Do you mean c is a prime?

    It doesn't look like somethiing I've seen before. The two systems I know of that use prime moduli are ElGamal and Diffie-Hellman. You may want to look into those.

    In the meantime, how is this system used? what's secret? what are you trying to predict?

  3. #3
    הבּרוּ נשׂאי כּלי יהוה mike's Avatar
    Join Date
    Mar 2001
    Posts
    491
    If you want to calculate b given a and x, that's discrete log and is hard unless phi(c) is smooth. If you want to calculate a given b and x, that's taking roots and is easy if c is a prime or if you know the factorization of c. Assuming c is a product of large primes, the problem is difficult.

    BUT if you just need to find any a,b such that a^b mod c = x, you're in luck. Just pick a=x^-b = inv(x)^b where inv(x) is the inverse of x mod c. Pick anything you want for b.

    Are there any other constraints on a? Like it has to be all ascii or something?

  4. #4
    Opti
    Guest

    Smile Opps DAM %$^$%^&

    Oh Man I Feel A Fool Now!!

    I Was Using A Tool For Factoring And Seems There Is A
    Problem With Its Hex To Decimal Conversion And Was Giving Me
    False Results

    I Entered (c) Again As A Decimal Number And Like U Mentioned
    Above (c) Is In Fact A PRIME And (a) & (b) Are Not Products
    Of Primes, God Iv Been Scratching My Head On This For
    2 Days ( Now It Seems To Fit The Pattern Of ElGamal With (c)
    being a Prime

    The Only Constraints I See At The Moment Are (a) & (b) Are 48 Bits

    What U Say Above Confuses Me Somewhat As I've Only Really Looked Into
    Number Theory In The Last 2 Days When I Came Across This Problem

    Think Im Gonna Read Up Some More On ElGamal And How Its Implemented
    In This Occasion And Work Out What Values I Have Now From That Method
    And How To Reverse It In Code

    Opti
    I promise that I have read the FAQ and tried to use the Search to answer my question.

  5. #5
    הבּרוּ נשׂאי כּלי יהוה mike's Avatar
    Join Date
    Mar 2001
    Posts
    491
    OK, c is prime. That can be good or bad, depending on how we attack it.

    Good news is that taking roots (like square root) is easy mod a prime. So if you have b,x,c, finding a is easy.

    Bad news is that discrete log is hard unless phi(c) is smooth. Since c is prime, phi(c)=c-1. If c-1 has lots of small factors, then you can do it, but it probably won't. So if you have a,x,c, finding b is hard.

    Either way, you still haven't said what constraints there are on a,b. Can you put in whatever values you want? If so, then it's easy to find a,b such that a^b=x mod c. Just choose any nonzero value for b and calculate a=inv(x)^b mod c.

  6. #6
    Opti
    Guest
    (a) & (b) Are Positive Integer Values No Longer Than 48Bits And (b)
    Cant Be 1 For Obvious Reasons, But I Do Need To Examines This Section
    Of The Code More And I Know Its Upto 1 or 2 Things Before The ExpMod
    Function, But Yes They Can Be Pretty Much Any Value

    Yeah c-1 Has Only 2 Factors So I Take It That Discrete Log Method
    Is Out Of The Window

    The Other 2 Methods U Mention Do Sound As Though They Would Work
    In This Instance

    Is It Possible U Could Explain Them A Little Bit More Or Paste An
    Example, I Will Look On The Web Also, I Do Understand Square Root,
    Would I Have To Repeat This In A Loop ?

    The Other Method Does Seem Alot Clearer To Me The Only Thing I Have
    Trouble With Is The inv(x) Bit, I Tried To Figure It Out In Mathematica
    But I Dont Understand How U Inverse (x) , I Thought x^-1 Was The Inverse, I Guess Id Better Read Some More On Basic Number Theory
    And How All This Stuff Fits Together

    Thanx For The Info So Far
    I promise that I have read the FAQ and tried to use the Search to answer my question.

  7. #7
    הבּרוּ נשׂאי כּלי יהוה mike's Avatar
    Join Date
    Mar 2001
    Posts
    491
    (a) & (b) Are Positive Integer Values No Longer Than 48Bits And (b) Cant Be 1 For Obvious Reasons
    Sorry, they're not obvious to me. I can't recall any reason why you can't pick any value you want for b. By the way, how long is c?
    Trouble With Is The inv(x) Bit, I Tried To Figure It Out In Mathematica But I Dont Understand How U Inverse (x) , I Thought x^-1 Was The Inverse
    inv(x) is x^-1, but you have to do it modulo c, so in Mathematica you'd use

    PowerMod[x, -1, c]

    Square root is also built in to Mathematica. Just say

    SqrtMod[a, c]

    Only half of the numbers have square roots mod c; these are called quadratic residues. You can tell if a number is a QR mod c by checking if a^((c-1)/2)==1. If it's 1, it's a QR; if it's c-1, it's not, so it doesn't have a square root mod c.

    I'm fairly sure one can extend this to higher roots, but I don't have algorithms on hand.
    Last edited by mike; June 19th, 2002 at 18:29.

  8. #8
    Opti
    Guest
    Well c Uses 6 Bytes So 48 Bits, Infact a b c x All Use A Max Of 48 Bits
    Im Pretty Sure b Cant Be 1 As That Would Be Easy To Solve As You Would Only Have To Make

    a = c+x Raising That To A Power Of 1 And MOD c Would Return x

    I Have Found A Couple Of Nice Pages I Need To Study More

    h**p://sicp.ai.mit.edu/Fall-1999/psets/ps2web/ps2-public/ps2-public.html
    h**p://w*w.farcaster.com/papers/crypto-field/field.html

    Covering Elgamal And Discrete Logarithms And I Noticed MIRACL Contains 2 Sources
    For Solving Discrete Log For Small Primes So That Should Be Useful

    Im Thinking Now If I Gather More Variables And The Algo Is Truely Elgamal
    I *Might* Be Able To Produce The Secret Key (x) Then With The Info From Above
    Make a And b To Fit That And Totally Reverse It

    Anyways All Interesting Stuff
    I promise that I have read the FAQ and tried to use the Search to answer my question.

  9. #9
    הבּרוּ נשׂאי כּלי יהוה mike's Avatar
    Join Date
    Mar 2001
    Posts
    491
    Well c Uses 6 Bytes So 48 Bits
    Hahaha! (Tears roling down cheeks)

    If they're ALL 48 bits, then the programmer had no idea what he was doing. At 48 bits your pc could crack it in a few seconds even if the rest of it was designed well. I bet he had so little idea what was going on that if you choose a=x, b=1 then it will work.

Bookmarks

Posting Permissions

  • You may not post new threads
  • You may not post replies
  • You may not post attachments
  • You may not edit your posts
  •