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/

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?

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?

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

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.

(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

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?
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.

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

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.