What Did You Learn Today 2.0

[Fireball]

I've recently become interested in understanding the theory underlying RSA encryption/decryption.  As a result, I learned about RSA via one of my books on number theory.  I enjoyed learning about the derivation of the decryption scheme from the encryption scheme, as it made use of Euler's theorem and multiple congruence properties to achieve the desired derivation.  There was also a second case of the derivation, which required one to make use of the fact that if a, b, and c are integers with gcd (a,b)=1 and a divides c and b divides c, then ab divides c; I've made use of this fact countless times when doing proofs in number theory.  

I actually started my exploration of Cryptography via the Caesar Cipher, since my number theory text started with it.  Basically, each letter in the alphabet is converted into an equivalent two digit number. The letter to numbers table goes as follows: 

A=00;  B=01; C=02; D=03; E=04; F=05; G=06; H=07; I=08

J=09; K=10; L=11; M=12; N=13; O=14; P=15; Q=16; R=17

S=18; T=19; U=20; V=21; W=22; X=23; Y=24; Z=25

We use the Caesar cipher as follows: suppose that we want to encrypt the plain text word "Yogi". 

Encryption

1) We convert each letter of the word to its two digit number: Y=25, O=14, G=06, I=08, so our message is expressed numerically as 25 14 06 08 (the spaces are for convenience). 

2) We then add 3 to each individual two digit number: 25+3=28, 14+3=17, 06+3=09, 08+3=11, so the encrypted message is now 28 17 09 11.  Now, if we obtain a number that is greater than 25, then subtract 26 from it and this will produce the desired encrypted number.  Thus, 28 – 26=02.  We now substitute 02 for 28 and the encrypted message is 02 17 09 11.  Converting this to letters gives the encrypted text CRJL.

Decryption

1) To decrypt the word CRJL, we convert each letter to its two digit number: C=02, R=17, J=09, L=11, so our message is expressed numerically as 02 17 09 11.  

2) We then subtract 3 from each individual two digit number: 02 – 3= –1, 17 – 3=14, 09 – 3=06, 11– 3=08, so the decrypted message is 

–1 14 06 08.  Now, if we obtain a number that is less than 0, then add 26 to it and that will produce the desired decrypted number.  Thus, –1+26=25. We now substitute  25 for –1 and the decrypted message is 25 14 06 08. Converting this to letters gives YOGI.

For anyone who is interested in practicing, here are some words that can be decrypted using the method described above:

(1) IUHHGRP

Show ContentSpoiler:

FREEDOM

(2) CDQB

Show ContentSpoiler:

ZANY

P.S. In math-speak, the actual representation for the encryption scheme is P+3≡C (mod 26) where P is the two digit plain text number and C is the two digit encrypted number.  The decryption scheme is represented as C – 3≡P (mod 26).

  Hmm. I didn't realize there was going to be math in here today. Just poking at you, Kernel.  I'm currently reading "The Golden Ratio", by Mario Livio. it's quite interesting. I used to do all kinds of substitution ciphers with friends as a kid. Letters and numbers both.

[Kernel Sohcahtoa]

I learned more about the basic cryptography that is used in cyber security via multiple videos by Mike Meyers.  It was interesting to get more underneath the various types of cryptographic attacks: for the purposes of an instructional simulation, Meyers would use a particular program to perform dictionary, brute force, and rainbow table attacks.  Watching these videos gave me more of an appreciation for using more complicated passwords.  I also enjoyed his references to the math involved in the various encryption/decryption schemes. In particular, IMO, elliptical curve cryptography is pretty neat.

[mordant]

I learned more about the basic cryptography that is used in cyber security via multiple videos by Mike Meyers.  It was interesting to get more underneath the various types of cryptographic attacks: for the purposes of an instructional simulation, Meyers would use a particular program to perform dictionary, brute force, and rainbow table attacks.  Watching these videos gave me more of an appreciation for using more complicated passwords.  I also enjoyed his references to the math involved in the various encryption/decryption schemes. In particular, IMO, elliptical curve cryptography is pretty neat.

Would you mind pointing me to the videos you speak of? My stepson is a math and physics whiz, and I think this might be something to help drive his understanding of software development. I am a line-of-business backend developer, and have never done dev work that really required more than to understand high school-level algebra, so I'm at a bit of a disadvantage in finding interesting (to him) problems for him to work on independently. This might be the ticket.

[Fireball]

I'd be interested as well. My eldest son is studying cyber security atm.

[Kernel Sohcahtoa]

I learned more about the basic cryptography that is used in cyber security via multiple videos by Mike Meyers.  It was interesting to get more underneath the various types of cryptographic attacks: for the purposes of an instructional simulation, Meyers would use a particular program to perform dictionary, brute force, and rainbow table attacks.  Watching these videos gave me more of an appreciation for using more complicated passwords.  I also enjoyed his references to the math involved in the various encryption/decryption schemes. In particular, IMO, elliptical curve cryptography is pretty neat.

Would you mind pointing me to the videos you speak of? My stepson is a math and physics whiz, and I think this might be something to help drive his understanding of software development. I am a line-of-business backend developer, and have never done dev work that really required more than to understand high school-level algebra, so I'm at a bit of a disadvantage in finding interesting (to him) problems for him to work on independently. This might be the ticket.

The videos were part of Mike Meyers' COMPTIA Security + course on Udemy and were in his cryptography section.  

I found these free Mike Meyer's videos on Youtube, which are part of his Security + course.

[Alan V]

I learned that scientists think direct-collapse black holes are possible. Instead of black holes only being formed by the collapse of huge stars, they could under certain conditions be formed directly by the collapse of clouds of gas, bypassing the star phase. Scientists think this the likely explanation of why so many super-massive black holes formed early in the universe, per their observations of quasars, well within a billion years after the big bang.

[Kernel Sohcahtoa]

Last night I decided to learn/explore an additional proof exercise on RSA encryption that was in one of my Elementary Number Theory Texts. For anyone who is interested, my proof is below.  I've placed sections of this post in spoiler tags in order to make the reading easier.

The below proof is my own effort of the exercise.  If I’ve made any error or typo, I’d be grateful if it could be pointed out to me, and I will correct it as soon as possible.  Also, for anyone who is interested, I’d be happy to answer any questions/clarifications about the proof below. Thanks.

Exercise

Assume all notation in the RSA encryption Scheme.  Let d’ be the inverse of e modulo lcm (q – 1, r – 1).  Prove that (d’, m) acts as a decryption key (please note that d’ is a positive integer) (Strayer, section 8.2, exercise 12, pg. 238).

RSA encryption scheme 

The public encryption key is (e,m) where m = qr and r and q are distinct odd primes and e is a positive integer with the property that gcd (e, (q – 1)(r – 1)) = 1.  The encryption scheme is P^e ≡ C (mod m) where P represents plaintext and C represents cipher-text such that 0 ≤ P < m and 0 ≤ C < m. (Strayer, 235-238).

Main definitions and facts that are used in the proof

Show ContentSpoiler:

Definition 1:

let n be a fixed positive integer and suppose a and b are integers.  If n divides a – b,  then

a ≡ b (mod n); the converse is also true. (Burton, 63)

Definition 2 (definition of divisibility):

suppose a and b are integers. If a divides b, then there exists an integer n such that b = an.

Definition 3: Properties of exponents 

Let x be an arbitrary positive number and suppose a and b are real numbers. Then x^(a + b) = (x^a)*(x^b). (Johnsonbaugh & Pfaffenberger, pg 57)

Definition 4: Greatest Common Divisor (GCD)

Suppose a and b are integers, not both 0.  Then gcd (a, b) is the greatest positive integer that is a common divisor of a and b

(Chartrand, Polimeni, and Zhang pg. 271)

Definition 5: Least Common Multiple (LCM)

Suppose a and b are positive integers.  Then LCM (a, b) is the least positive integer m such that a divides m and b divides m
(Strayer, 28)

Show ContentSpoiler:

Fact 1: divisibility properties

Let a, b, and c be integers. Then the following properties hold:

A)     If a divides b and b does not equal 0, then |a|≤ |b|

B)      If a divides b and a divides c, then a divides bx + cy for all integers x and y. (Burton, 20)

Fact 2:

Let a, b , and c be integers with gcd (a, b) = 1.  If a divides c and b divides c, then ab divides c (Burton, 23).  Suppose that we have fixed positive integers m and n with 

gcd (m, n) = 1 such that m divides a – b and n divides a – b.  Then via fact 2, mn divides a – b.  We can express this example in the following equivalent way: 

if a ≡ b (mod m) and a ≡ b (mod n) with gcd (n, m) = 1, then a ≡ b (mod mn) (here we translated fact 2 into the language of definition 1).  This equivalent way of looking at fact 2 will ultimately be used to prove the exercise.

Fact 3: Congruence properties

Let n be a fixed positive integer and a, b, c, and d be arbitrary integers.  Then the following properties hold:

A)     a ≡ a (mod n)

B)      if a ≡ b (mod n), then b ≡ a (mod n)

C)      if a ≡ b (mod n) and b ≡ c (mod n), then a ≡ c (mod n)

D)     if a ≡ b (mod n) and c ≡ d (mod n), then ac ≡ bd (mod n)

E)      if a ≡ b (mod n) and j is a positive integer, then a^j ≡ b^j (mod n) (Burton, 65)

Fact 4: Fermat’s Theorem

Let p be prime and suppose gcd (a, p) = 1.  Then a^(p – 1) ≡ 1 (mod p) (Burton 88)

Fact 5: Multiplicative inverse modulo n

Let n be a fixed positive integer and let c be an integer such that gcd (c, n) = 1.  Then the linear congruence cx ≡ 1 (mod n) has a unique solution modulo n.  This solution is called the inverse of c modulo n.  (Burton, 77).  Let d be the inverse of c modulo n.  Then cd ≡ 1 (mod n), which implies that n divides cd – 1 (this is the converse of definition 1).  Via the definition of divisibility, this means that  cd – 1 = nj for some integer j.  We can rewrite this as cd = nj + 1 (we will utilize this fact in the proof. Please note that if 
c and d are positive integers, then j must be a positive integer; this is how it will be in the proof)

Fact 6: LCM and GCD relationship

If a and b are positive integers, then gcd (a, b)*lcm (a, b) = ab   (Burton, 30)

 

Proof

Show ContentSpoiler:

Our goal is to show that (d’, m) acts as a decryption key.  This can be accomplished by showing that C^d’ ≡ P (mod m): this congruence represents the decryption scheme from the cipher-text to the plain-text of the original message, so if we can establish the congruence C^d’ ≡ P (mod m), then it follows that (d', m) acts as a decryption key.  We will establish C^d’ ≡ P (mod m) by showing that C^d’ ≡ P (mod q) and C^d’ ≡ P (mod r).
 
Via the hypothesis, d’ is the inverse of e modulo lcm (q – 1, r – 1), that is, ed’ ≡ 1 (mod lcm (q – 1, r – 1)).   Let f= gcd (q – 1, r – 1).  Using the fact that 
lcm (q – 1, r – 1) = (q – 1)(r – 1)/f, we can write ed’ ≡ 1 (mod (q – 1)(r – 1)/f), which is equivalent to ed’ = [(q – 1)(r – 1)/f]k + 1 where k is a positive integer.  
Now, the encryption scheme is P^e ≡ C (mod m), which implies C ≡ P^e (mod m), and so, C^d’ ≡ P^(ed’) (mod m). 
Thus, C^d’ ≡ P^([(q – 1)(r – 1)/f]k + 1)  (mod m), that is, C^d’ ≡ PP^([(q – 1)(r – 1)/f]k)  (mod m) (1).  We will consider two cases.

Show ContentSpoiler:

Case One: gcd (P,m) = 1

Then gcd (P,q) = 1.  Via Fermat’s theorem, P^( q – 1) ≡ 1 (mod q).  Consequently,  P^([(q – 1)(r – 1)/f]k) ≡ 1^([( r – 1)/f]k) = 1 (mod q), that is, 
P^([(q – 1)(r – 1)/f]k) ≡ 1 (mod q), and so, PP^([(q – 1)(r – 1)/f]k) ≡ P (mod q). Also, gcd (P,r) = 1, so via Fermat’s theorem, P^( r – 1) ≡ 1 (mod r).  
Consequently, P^([(r – 1)(q – 1)/f]k) ≡ 1^([( q – 1)/f]k) = 1 (mod r), that is, P^([(r – 1)(q – 1)/f]k) ≡ 1 (mod r), and equivalently, we can write 
P^([(q – 1)(r – 1)/f]k) ≡ 1 (mod r).  Thus, PP^([(q – 1)(r – 1)/f]k) ≡ P (mod r).  Hence, PP^([(q – 1)(r – 1)/f]k) ≡ P (mod q) and PP^([(q – 1)(r – 1)/f]k) ≡ P (mod r) implies 
PP^([(q – 1)(r – 1)/f]k) ≡ P (mod qr), that is, PP^([(q – 1)(r – 1)/f]k) ≡ P (mod m) (2).  Combining congruences (1) and (2) gives C^d’ ≡ P (mod m).  This completes the case.

Show ContentSpoiler:

Case Two: gcd (P,m) > 1

Then since 0 ≤ P < m and r and q are distinct odd primes, either gcd (P, m)= q or gcd (P, m) =r (please note that gcd (P, m) cannot equal rq=m, because this implies that m divides P which implies that m ≤ P which contradicts the fact that P < m). Without loss of generality, let gcd (P, m) = q, which implies that gcd (P, r) must equal 1 
(if gcd (P, r)= r, we have q divides P and r divides P, and since gcd (q, r)= 1, then qr=m divides P, a contradiction).  
Thus, q divides PP^([(q – 1)(r – 1)/f]k)  and q divides P, which implies q divides PP^([(q – 1)(r – 1)/f]k)  – P, which implies PP^([(q – 1)(r – 1)/f]k) ≡ P (mod q). 
Since gcd (P,r) = 1, then via our work in case one, we can apply Fermat’s theorem and  ultimately obtain the congruence PP^([(q – 1)(r – 1)/f]k) ≡ P (mod r). Hence, we have PP^([(q – 1)(r – 1)/f]k) ≡ P (mod q) and PP^([(q – 1)(r – 1)/f]k) ≡ P (mod r), which implies PP^([(q – 1)(r – 1)/f]k) ≡ P (mod qr), that is,
 PP^([(q – 1)(r – 1)/f]k) ≡ P (mod m), which is congruence (2).

As in case one, combining congruences (1) and (2) gives  C^d’ ≡ P (mod m).  This completes the case.

Show ContentSpoiler:

In conclusion, our goal was to show that (d’,m) acts as a private key.  This can be shown by establishing that C^d’ ≡ P (mod m).  Hence, in both cases, we established that C^d’ ≡ P (mod m), which completes the proof.

 
References

Burton, David M. (2011). Elementary Number Theory, 7th ed. (Indian edition). Chennai: McGraw Hill.

Chartrand, Gary; Polimeni, Albert D; and Zhang, Ping. (2013). Mathematical Proofs: A Transition to Advanced Mathematics, 3rd edition. New York: Pearson. 

Johnsonbaugh, Richard and Pfaffenberger, W.E. (2002). Foundations of Mathematical Analysis. New York: Dover Publications.

Strayer, James K. (1994). Elementary Number theory.  Illinois: Waveland Press.

[Red Belt]

I don't do much learning and most of what i learn i quickly forget.

[GenesisNemesis]

Watched an episode of The Planets on PBS, and they mentioned that as the Sun expands as a Red Giant in a couple billion years or so, it could warm Titan's climate and melt ice, which would mean liquid water could flow on Titan, and life could evolve on Titan. Fascinating to think that, potentially, if that life becomes sentient, they would never know that Earth existed. Not sure how long life could exist on Titan before Titan is engulfed by the Sun though (and obviously this is all speculation, but still fascinating).

[Vera]

About analysis paralysis (and extinct by instinct): an individual or group process when overanalyzing or overthinking a situation can cause forward motion or decision-making to become "paralyzed", meaning that no solution or course of action is decided upon. A situation may be deemed as too complicated and a decision is never made, due to the fear that a potentially larger problem may arise. A person may desire a perfect solution, but may fear making a decision that could result in error, while on the way to a better solution. Equally, a person may hold that a superior solution is a short step away, and stall in its endless pursuit, with no concept of diminishing returns. On the opposite end of the time spectrum is the phrase extinct by instinct, which is making a fatal decision based on hasty judgment or a gut reaction.

The basic idea has been expressed through narrative a number of times. In one "Aesop's fable" that is recorded even before Aesop's time, The Fox and the Cat, the fox boasts of "hundreds of ways of escaping" while the cat has "only one". When they hear the hounds approaching, the cat scampers up a tree while "the fox in his confusion was caught up by the hounds". The fable ends with the moral, "Better one safe way than a hundred on which you cannot reckon".

I need to learn how to overcome it but I feel... paralysed (and I'm only mildly joking...)

Relatedly: The centipede's dilemma:

"A centipede was happy – quite!
Until a toad in fun
Said, "Pray, which leg moves after which?"
This raised her doubts to such a pitch,
She fell exhausted in the ditch
Not knowing how to run."

[Vera]

About Lunchables. This looks positively vile. Why would you feed this to a child? To any living creature, really, but about above all, a child? Really?!

[Fireball]

About Lunchables. This looks positively vile. Why would you feed this to a child? To any living creature, really, but about above all, a child? Really?!

Sloth. And convenience. My children never got fed that kind of stuff. My eldest son had heard of "Cheez-Wiz" and asked my wife to buy some. None of the other boys liked it, either.

[grympy]

About Lunchables. This looks positively vile. Why would you feed this to a child? To any living creature, really, but about above all, a child? Really?!

Sloth. And convenience. My children never got fed that kind of stuff. My eldest son had heard of "Cheez-Wiz" and asked my wife to buy some. None of the other boys liked it, either.

Today I learned that I REALLY need to turn on the a/c when inside  temperature is 15c  (59F).   I have the a/c set at 21C (69F)
I hate being cold, thank the FSM it NEVER snows in this city. 

 Don't know if I should be expecting some more rude shocks from climate change .So  far it's been hotter summers. As a kid, average summer temperature was mid 80's F ,with 90F being the hottest it usually got, very rarely hit 100F. Recent  years, we've had a week at a time at 100 and above, maxing at about 107F.  Last year, during one of those heat waves, it reached 122F, hottest day on record. I was expecting rolling power cuts to relieve demand  on the grid. Didn't happen. I was so pleased I could have just shit. 

I've said it before and I'll say it again; we're fucked.

[GenesisNemesis]

That Mike Myers also played Fat Bastard. Yes, it took me that long to learn that.

[skyking]

Learned that the hatchback latch on my car can get to an un-openable state, and that I will be cutting said latch off with a sawzall and replacing it.

[Dānu]

There are whole websites devoted to reviews of instant noodle dishes like ramen.

[Gwaithmir]

Gene Hackman is still alive at 89. 

[Chas]

I just learned that Mathilda staged a coup, Aliza disappeared and has been replaced by an AI, undoubtedly created by Mathilda.

[Vera]

That the word cretin comes from the word christian. Talk about truth in advertising.

Yesterday I learnt about Anna's eighty-eight, which is a pretty cool little critter.



And some time ago I learnt that there is a whole species named Clitoria.

[Vera]

About sea silk.

"An extremely fine, rare, and valuable fabric that is made from the long silky filaments or byssus secreted by a gland in the foot of pen shells (in particular Pinna nobilis).The byssus is used by the clam to attach itself to the sea bed.

The cloth produced from these filaments can be woven even more finely than silk, and is extremely light and warm; it was said that a pair of women's gloves made from the fabric could fit into half a walnut shell and a pair of stockings in a snuffbox."



(And, obviously, about byssus.)

[Vera]

The Bulgarian word for bedsheet, which, unsurprisingly, comes from Turkish, basically means night chador

I feel like I've been using bedsheets wrong all my life.

[Dānu]

Mountain Dew contains an ingredient that is a patented flame retardant.

[Fireball]

Mountain Dew contains an ingredient that is a patented flame retardant.

 

Water and CO2

[Vera]

About brain sand: "calcified structures in the pineal gland and other areas of the brain such as the choroid plexus. Older organisms have numerous corpora arenacea, whose function, if any, is unknown. Concentrations of "brain sand" increase with age, so the pineal gland becomes increasingly visible on X-rays over time, usually by the third or fourth decade."

And here I was, thinking my brain was slowly turning to mush...

[Dānu]

About brain sand: "calcified structures in the pineal gland and other areas of the brain such as the choroid plexus. Older organisms have numerous corpora arenacea, whose function, if any, is unknown. Concentrations of "brain sand" increase with age, so the pineal gland becomes increasingly visible on X-rays over time, usually by the third or fourth decade."

And here I was, thinking my brain was slowly turning to mush...

I forget exactly what it was, probably eating meat, but there was a member of an odd Hindu sect that repeatedly argued on AF that the correlation was a sign that eating meat, if that's what it was, was bad for you, because he believed the pineal gland had a special role in linking our consciousness to the cosmic consciousness that is the universe, because, after all, we all know that we are but a figment in its imagination. Surprisingly he was decent at debating. Not surprisingly, the weakness of the basis for his beliefs forced him to take the low road in an argument on many occasions.