Alice and Bob - why does it work?

Let's forget Eve, my question is simply why do Bob and Alice arrive at the same key?

They agree on 7^x(mod11)
A's secret number is 3, she tells Bob a=2
B's secret number is 4, he tells Alice b=3
B^a(mod11) & A^b(mod11) are both 5
Why?
It's probably something super simple my brain refuses to compute so please
HELP

a reply to: Peeple

Looks reminiscent of Euclid algorithms. Pretty stoned at the moment and havent worked on anything like that since college 30 years ago.

a reply to: Peeple

Remainder math can be confusing for those that are not forced to deal with it as homework!!

The prime numbers 7, 11, are the key. So you have the following as primes... [2, 3, 5, 7, 11, 13, 17, ...]

That are both prime and have nothing between them except 7 + 11 = 18. But the “mod 11” should knock it back to just ‘7’ but we end up at 5. Hum?

It shouldn’t be if you use modulus arithmetic correctly! Anything, 7 + 11 (mod 11) = 5 does not work! If there is more calculations involved, fine. But you are adding lemon zest to a recipe and then sifting it out (as you have described!).

You are not crazy but we seem to be missing a step.



ETA: OK. Powers. It is a 3/4/5 triangle. Basically the hypotenuse! That is what we missed.

a reply to: TEOTWAWKIAIFF

TEOT! I was hoping you'd come to the rescue.
It's an encryption problem the Diffie-Hellman algorithm alas I'm lacking maths (again)!

I imagine mod11 as a clock with 11 hours? But I don't know how to tackle it in an equation?
And this ^ is the power sign no?
So my problem is, I don't understand why A^b(mod11)=B^a(mod11)=X^AB(mod11)
In my example it's all 5 WHY
I tried to make equation with replacing b=X^B(mod11) and a=X^A(mod11) but that ended in chaos because I don't know the rules.
I just want to know why if they share X, a & b they get the same key

And Yes I know it's much more complicated with mod26579432 or whatever, I stick to 11 because convenience.

I thought I was smart. Then I read this thread.

a reply to: Trueman

Sorry I didn't do a really good job expressing myself I guess.

Let's see if I got this right.

^ is 'in the power of'
mod(x) is 'what remains after dividing by x'

So:

4^2 = 4*4 = 16
mod by 11 and you have 5 left

3^3 = 3*3*3 = (3*3)*3) = 9*3 = 27
mod by 11 and you have 5 left

Hope this helps.

-FL

a reply to: Flawless Logic

No, I know that.

What I don't get is:
Bob has a secret number B, he puts that in the public function 7^B(mod11)=b
Alice does the same 7^A(mod11)=a
They exchange their results a & b , put that in their function respectively with their secret numbers A&B
A^b(mod11) and B^a(mod11) to get the encryption key in this case 5
I don't understand why
B^a(mod11)=A^b(mod11)=7^AB(mod11)=5
Basically my question is the path of solving the equation
How it is possible that their secret number to the power of the public number mod11 is the same as the public function to the power of the product of their secret numbers.

I get what you are asking now.

I thought I had the answer, but it only worked with certain variables. (Yours being among them)

Please do share if you find an in-depth explanation.
Best of luck.

-FL

originally posted by: Peeple
a reply to: Trueman

Sorry I didn't do a really good job expressing myself I guess.

No matter how you put that, it'll be like looking at one old Egyptian wall for me.

First I thought it was a joke like Abbott&Costello's "who's in first base".

This looks like the Diffie-Hellman procedure, used when securely logging into sites.

The key to D-H is that it has the Commutative property, just like multiplying numbers. i.e. a X b = b X a

a reply to: Peeple

They agree on 7^x(mod11)
A's secret number is 3, she tells Bob a=2
B's secret number is 4, he tells Alice b=3
B^a(mod11) & A^b(mod11) are both 5
Why?

While I have absolutely no idea who Bob and Alice are, or why they are working in mod11, the math I can explain... you'll have to handle the context yourself.

Any multiple-digit number is simply an extension of the base used in creating it. For example, let's take the number 43. We use base10 (10 digits on both hands), so we interpret that as (4*10)+3. The number written 43 in base11 would be (4*11)+3 = 47 in mod10, and the number 43 base10 is the same as the number 3A (3*11+A (A=10, see below)) base11.

Single digit numbers are simple to work... in base10, the single digit numbers are 0, 1, 2, 3, 4, 5, 6, 7, 8, and 9. In base11, they are 0, 1, 2, 3, 4, 5, 6, 7, 8, 9, and A ('A' being a symbol for the 11th numeral (A base11=10 base10) since we don't have one ready-made... same principle as using A-F to do hexadecimal (base16)).

Modulus arithmetic is based on the remainder of a number divided by the base. As an example, 43 mod10 is 3 because 43/10 = 4.3, or 4 with a remainder of 3. It works out that the final digit in a base is also always the modulus in that base.

So to do the calculations above, we first convert to base10. Easy enough, as the single-digit numbers 0-9 are already the same in base10 as in base11. 2 base11 = 2 base10; 3 base11 = 3 base10; 4 base11 = 4 base10.

Now we do the actual calculations in base10: B^a = 4^2 = 16 base10. A^b = 3^3 = 27 base10.

Now we convert back to base 11. 16/11 = 1 and 5/11 (remainder 5), or 15 base11; 27/11 is 2 and 5/11 (remainder 5), or 25 base11. Take the last digit as the modulus and both are equal to 5 mod11.

Hope that helps.

TheRedneck

a reply to: Darkstar2

Yes it is. I'm just not getting why it has that because A and a as well as B and b are not the same numbers.

a reply to: TheRedneck

So if I want to handle them in an equation I simply write them as fractions and all is well?
I'll try that.
That would be really facepalm worthy on my end if it works...

It's of course not true if you keep the full fraction but it makes sense now.
In my example
(7^A mod11)^B mod11 = (7^B mod11)^A mod11

Modus operandi found.
Thanks for humiliating me

a reply to: Peeple

Well, the whole point of using modulus is to not have to deal with them as fractions. But there's several different ways to handle such equations. What I gave was a rather lengthy explanation to demonstrate how modulus doesn't have to be a lengthy process, lol. You use what works for you.

I think where a lot of people get confused is they try to work the problem in base11. That's possible, but it can also be a bit laborious and requires a good understanding of different bases.

Your statement above about imagining mod11 as a clock with 11 hours is spot on. In reality, we use a base12/base60 system for measuring time anyway, so it's a good way to point out how the modulus works. You could think of mod11 as such a clock and move one "hour" for every count. When you're finished, whatever hour you are pointing to is the modulus. How many times that clock went around before you finished is the complete number.

You can also just divide and subtract, like this. Divide the first result (16) by 11 to get 1.4545. Now take the whole part of that, the 1, and multiply it by the 11 to give 11. Subtract that 11 from the original 16 and you'll get 5. Same with the 27... 27/11 = 2.4545. The whole part of 2.4545 is 2, so 2*11 = 22. 27-22 = 5, which is the modulus using base11.

Once you realize how our base10 system works, other bases become a lot easier to understand. Unfortunately, this is not normally taught in schools outside "advanced" math courses which no one seems to want to take. In truth, math is the easiest subject there is in school, but it is taught in a haphazard fashion instead of a logical progressive fashion.

Take the number (in base10) 45,692 (forty five thousand six hundred ninety two). How that number comes about using the various digits is as follows: imagine five columns, containing, in order, 4, 5, 6, 9, and 2 reading left to right. Now imagine each column having a number itself... the 4 is in the 5th column, the 5 is in the fourth column, the 6 is in the third column, the 9 is in the second column, and the 2 is in the first column. Yes, they are in reverse order, because the first column is to the left of the decimal point, which in this case comes after the 2.

The 4 is in the fifth column, so it means 4*(10^4). The 5 is in the fourth column, so it means 5*(10^3). The 6 is in the third column, so it means 6*(10^2). The 9 is in the second column, so it means 9*(10^1), and the 2 is in the first column so it means 2*(10^0). Notice that we drop the column number by 1 in every case; that's because we start counting powers from 0, not from 1 like the columns. Now put it all together and we get (4*10,000)+(5*1000)+(6*100)+(9*10)+(2*1) = 45,692.

Schools teach about the value of the columns, but they don't make that connection that they are just powers of the base (10) in sequence.

Now apply that to base 11. The columns are still numbered the same way, but they represent powers of 11 instead of powers of ten. If we try to convert 45,692 base11 to base 10, we get (4*11^4)+(5*11^3)+(6*11^2)+(9*11^1)+(2*11^0) = (4*14,641)+(5*1331)+(6*121)+(9*11)+(2*1) = 58,564+6655+726+99+2 = 66,046 base10.

Now you know why we don't use base 11 very much! LOL!

You can produce numbers in any base this way... it is possible to have base 5,832,853 if you want it. Just don't ask me to do the conversions!

TheRedneck

a reply to: TheRedneck

Well the point seems to be that it's an operation because 23/11=2.0909 and 23 mod11=1
So they're not equals, but the rule of fractions apply in solving the equation that was what I was looking for.
And thank you for the hint with the subtraction when using it with numbers.

a reply to: Peeple

Thanks for humiliating me

No, no, no humiliation. Just trying to help. Math is my forte; electronic engineering has some of the most horrendous mathematics of any of the engineering disciplines. Everything is mathematically modeled. In my Optimal Control class, the mathematics was so involved it could easily take months, literally, to solve one problem.

I am a firm believer that our public school system has disappointed us all, especially in the area of math. Every student graduating high school should be able to perform integration and understand the basics behind why mathematics works in general. Believe it or not, that is do-able! It just requires logical progression through the different aspects of the language. What I just gave you should be taught by the 4th grade, but unfortunately it is not. It is rather left for colleges to teach only to those who take STEM courses (and not all of them).

If my posts help a few people to understand a little more about the wonderful world of math, then I have accomplished something vital for society.

TheRedneck

a reply to: Peeple

The modulus can be equal even though the numbers are not.

Think back to the clock: 3 o'clock (3 mod12) might tell you what time of day it is, but not how many days it took to get there. There are many, many 3 o'clocks, one (two?) for every day, but all are the same time of day. The modulus works the same way; you can have an infinite number of numbers that resolve to the same modulus, but all end up at the same position between zero and the base.

There is also, at least theoretically, always a base where two numbers have the same modulus. After all, Xmod1 is always zero where X is an integer (whole number). That's what is known as a "trivial" answer (similar to anything times zero is still zero, doesn't tell you much), but it is always an answer. I'm sure somewhere, someone has made an equation for finding that base with identical modulii, but I can't rattle such an equation off the top of my head.

TheRedneck

a reply to: TheRedneck

Math and I never got that close, I'm more the linguistics type they said.
And it's all just "hobby" to me, an interest in basics of encryption, ufology and ancient mythology can lead you on mysterious paths.

But generally speaking I have a thing for mathmaticians, I marvel at their straight forward minds as others enjoy a concert...
Because I really do think it's not in everybody's predisposition to be good at maths as not everybody can achieve virtuosity in music.
And as true human I admire what I can't be.

But I'd fully support logics classes at school.

a reply to: Peeple

Math and I never got that close, I'm more the linguistics type they said.

That's the thing, though... math is a language! It's just much more precise and structured than most languages. In some ways, that makes it easier to speak and learn, but it can also mean it is less imaginative than, say, English. You are right that everyone has talents and weaknesses... I can't cook, to the point of making a sandwich is akin to Russian Roulette, lol... but I pick up on mathematical concepts and logic easier than most. I kid around with people that I am almost to the level of idiot savant.

Seriously... my wife has banned me from the kitchen unless something is broken... then I am allowed in only long enough to fix it. I don't know how she manages to make food from the stuff in there, but as you said, I admire her ability to do so.

I still say, though, that integration is something every high schooler can and should accomplish. maybe not to the extent a mathematician can handle, but enough to fully understand the concept. Linear Algebra, vector calculus, convolution of signals, that sort of thing can be handled by those with aptitude, but preparing students with a mathematical background is both possible and beneficial to an evolving society.

Virtuosity in music, now... good Lord, woman, you're talking to someone who considers themselves fortunate they can play a radio! My singing voice is classified by the NSA as a weapon of mass destruction!


TheRedneck