phi of n over 2 is just a number after all

Some people seem to have a hard time visualizing why my previous post is interesting. While proving the existence of a second private key does not break the RSA encryption algorithm, it does present a second attack vector especially for a certain subset of the set of products of safe primes.

Clearly, phi(n)/2 can be found if phi(n) is known. However, as I stated previously in this blog, for certain products of safe primes phi(n)/2 can be found without prior knowledge of phi(n).

In general, if n belongs to the set of these certain products of primes, then there exists an integer k mod n such that 2*k = n-1 and k^k = phi(n)/2 where phi(n) is Euler's Totient Function

One such product is the product of the 2 smallest safe primes, namely 5 and 7.


Given n = 35 then (n-1)/2 = 17 and 17^17 = 12, which is phi(35)/2


Proving The Existence Of A Second Private Key That Decrypts a Message Encrypted With The RSA Encryption Algorithm

While taking a course in cryptography 6 years ago I stumbled upon a problem that kept me awake at night for many nights.

In school we learn that the RSA encryption algorithm consists of one public key and one private key. I've asked several professors if there could be a second private key that decrypts all messages in the same way as the intended private key and I've always received a negative answer.

And yet I stumbled upon two private keys in one particular example. I delved into the Mathematics behind the RSA algorithm and I found out that in fact there are at least two keys in every single example. I not only managed to prove the existence of a second private key but I was also able to find two different formulas for obtaining the second key.

One of the formulas requires knowledge of phi(n)/2 where phi(n) is Euler's Totient Function.

If d1 is the intended private key and (n, e) is the public key then the second key d2 can be found using the following formula:

d2*e = phi(n)/2

Here's the full paper: https://marinaibrishimova.net/docs/otherkeys.pdf

Currently, I'm looking into ways of obtaining phi(n)/2 without having to factor n.


Products of Primes Without Selfie Powers

In my previous post I suggested that there are products of primes p and q that are easier (relatively) to factor because there is an integer k such that k = (p*q - 1)/2 and k^k = (phi(p*q))/2 and I called k a selfie power.

Before I talk about such products, I'll talk about products of primes, which have no selfie power and no semi selfie powers* because proper categorization is important.

Theorem: Given a product of primes p and q, if p or q divides phi(p*q) then p*q has no selfie power (ie an integer k such that k = (p*q - 1)/2 and k^k = (phi(p*q))/2 )

Proof: If p or q divides phi(p*q) then GCD(phi(p*q), k) = 1 since by definition of a selfie power k = (p*q - 1)/2 but also by definition of a selfie power k^k = (phi(p*q))/2 so 2*(k^k) = phi(p*q), which is a contradiction.

Example: Let p = 5 and q = 11, then p*q = 55 and phi(p*q) = (p-1)*(q-1) = 4*10 = 40 and clearly p divides phi(p*q). Furthermore, (p*q-1)/2 = 27 and 27^27 (mod 55) = 42 so 27 is not a selfie square as expected.

*to be defined in future blog posts


Selfie Powers

According to some people in Israel, the number 36 is special. According to these people, at any point in time there are 36 people who hold the world together and if one of them dies, then the world will fall apart. I don’t share such esoteric views but I do find the number 35, which is one less than 36, to be quite extraordinary from a mathematical point of view.

The exponentiation table of Z sub 35

It represents a special class of products of two distinct primes with peculiar properties. Such products of primes are really easy to factor. 

Before I talk more about other products of primes like this, first I have to introduce a new definition, which is not new to me but it is new to this blog.

Definition: Selfie powers are integers k mod n such that 2*k = n-1 and k^k = phi(n)/2 where phi(n) is Euler's Totient Function


Given n = 35 then (n-1)/2 = 17 and 17^17 = 12, which is phi(35)/2


A Few More Conjectures

The subset of safe primes, which I lovingly call "steady" primes are not so steady after all if my latest
conjectures turn out to be true.

As I wrote in a previous post, the set of safe primes is composed of two subsets: the set of steady primes and the set of tough primes.

The first few safe primes where primes in olive green are steady and the rest are tough

Conjecture 1: Given p a steady prime and a < p such that it is not a power of 2 mod p then
a^((p-1)/2)= p-1 else if a is a power of 2 mod p then a^((p-1)/2)= 1 

Conjecture 2: Given p a steady prime then (p-1)/2 is not a power of 2 mod p and
((p-1)/2)^((p-1)/2) = p-1


The Graphing Calculator

When I first moved to Canada I was simultaneously shocked and pleasantly relieved to find out that calculators are mandatory in high schools. 


Subsets of Safe Primes

The set of safe primes is composed of 2 mutually disjoint sets: the set of tough primes and the set of steady primes.

a list of the first few safe primes with tough primes in light blue background; the rest are steady primes

The main difference between these two sets lies in the structure of the exponentiation tables of their elements. For a tough prime p, I conjecture that:

Conjecture: If p is a prime of the form 8n+7, then the order of even powers of 2 mod p is p-1 and the order of odd powers of 2 mod p is (p-1)/2

In contrast, for a steady prime q I conjecture that:

Conjecture: If q is of the form 8n-1 such that 4n-1 and 8n-1 are also primes, then the order of all powers of 2 mod q is equal to (p-1)/2

Example: Let p = 11 and let q  = 7. Below are the corresponding exponentiation tables of Z11 and Z7.
The order of 2 mod 11 = 10, which is equal to the order of 8 mod 11, but the order of 4 mod 11 is half of that. Whereas in  Z7 the order of all powers of 2 is equal to 3.

Steady primes are the only primes where the order of all powers of 2 mod p is the same.  For all other primes the order of different powers of 2 is different.

On a slightly different note, as bad as safe primes may sound for cryptography, they are still not as bad as strong primes.


Steady Primes

Another interesting subset of the set of safe primes is the set of steady primes as defined below:

Definition: A steady prime is a safe prime p such that all powers of 2 mod p have order phi(p)/2 where phi() is Euler's Totient Function.

Example:  Let p = 23.

Using a calculator, it is easy to see that all unique powers of 2 mod 23 are 2,4,8,16,9,18,13,3,6,12,1 

Using another calculator, it is also easy to verify that the order of 2 mod 23, or the smallest integer k for which 2^k = 1 mod 23 is 11, the order of 4 mod 23 is also 11,  and so is the order of 8 mod 23, and this is the case for every other power of 2 mod 23 in the list above.

The first steady primes are 7,23,47,167,263,359,383,479,503,...

Conjecture: Steady primes are primes of the form 8p-1 such that 4p-1 and 8p-1 are also primes.

Claim: Given two steady primes p and q, the order of every power of 2 mod p*q is phi(p*q)/4

Claim: For all other safe primes q that are not steady primes, the order of at least one power of 2 mod q is at least 2 times less than the order of 2 mod q itself.

Below is a calculator for finding powers of any integer a mod n such that a < n.


Ghetto Superstar

Last year I visited the world's oldest ghetto, namely the Venetian Ghetto Nuovo. It is the first place in the world where the word ghetto was used to describe a poor segregated community.

The Venetian Ghetto is a part of Venice, Italy where gondolas don't go. That's what I was told when I approached a gondolier asking for directions.

When both Apple maps and Google maps failed to provide a coherent path to my desired destination as well, I had to resort to ancient technology: ask a local who is not in the transportation industry.

A store clerk from a local souvenir shop kindly provided me with the following map, and I somehow managed to find my way.

Venice is by far the most surreal place that I had the opportunity to visit.
An emergency vehicle 
Many parts of the city are only accessible by boat, and only emergency service boats are allowed to speed.

According to my slightly cryptic but nevertheless useful map, I had to go to the Grand Canal first and take a waterbus in the opposite direction from where I was initially headed to until reaching the edge of the city.

A waterbus stop near San Marco Square

The Grand Canal runs through the entire length of the Veneto region, which is composed of 117 small islands connected by bridges. The Venetian Ghetto is one of these islands.

Rialto Bridge, Venice

I got off near (what looked like) the edge of the city and I went down a small street, then up another small street, and then I somehow ended up on one of the bridges connecting the Venetian Ghetto with the rest of Venice.

At the other side of the bridge there is a tunnel that leads to the main square. The Venetian ghetto was once home to thousands of Sephardic and Ashkenazi Jews, mostly refugees from other parts of Europe where they were unwanted at one point or another.

Although there was a Jewish presence in Venice for centuries prior to the establishment of the Venetian Ghetto, they were not segregated until Venice saw an influx of Jews from Spain after the Alhambra Decree and from other parts of Europe with similar sentiments at the time.

For many of the Sephardic Jews fleeing Spain, Venice was merely a pit stop before reaching the Ottoman Empire.

The Venetian Republic began rounding up and confining Jews to a small island on the edge of the Veneto region on the 29th of March 1516. The island was home to ancient foundries.

There are several synagogues in the ghetto tucked away in common areas of unassuming buildings, and some of them are still in use today. All of them honoured the Venetian Republic in some way with their decor in addition to honouring Ashkenazi, Sephardic, and Italian Jewish tradition.

Sephardic Synagogue in the Venetian Ghetto: red and gold were the official colours of the Venetian Republic

The word ghetto as we know it today comes from an old Italian word for foundry pronounced as jetto (geto with a soft g as in jet). Apparently, the etymology of the word is a controversial topic but the most plausible theory is that Ashkenazi Jews had trouble pronouncing the soft g so they transformed it into a hard g effectively coining the word ghetto.

Life was not easy in the shanty part of town. Just like in the rest of the world at the time, Jewish people in the Venetian ghetto were only allowed to do the jobs that nobody else liked doing.

They were also not allowed to leave the ghetto at night and they had to wear identifiers that they were Jewish. Living quarters were cramped: large stories inside the buildings were separated into smaller ones to accommodate more people. Entire families were crammed inside single small rooms with low ceilings and sometimes no windows.

The view above the main plaza across from Museo Ebraico di Venezia where I learned about the history of the Venetian Ghetto

Although people who spent time in the ghetto endured many hardships, some of them and many of their descendants thrived and prospered in different parts of the world.

Meanwhile in Spain 500 years after a bill was passed to expel all Jews from the Iberian peninsula, a new bill was introduced to grant citizenship to the descendants of those who were expelled.


I Can Do Proofs

In my last entry I made a typo when describing a sequence using two different formulas.

The first formula is 2i + (2i-1 - 3) if i is even or 2i + (2i-1 + 3) if i is odd for all i > 2
The second formula is 3*(2i-1 - 1) if i is even or 3*(2i-1 + 1) if i is odd for all i > 2

I claim that these two formulas are equivalent.

It may look counterintuitive that if i is even then 2i + (2i-1 - 3) = 3*(2i-1 - 1) and that if i is odd then 2i + (2i-1 + 3) = 3*(2i-1 + 1) but I can actually prove it.

Below I provide a proof using mathematical induction to show off my mad skillz.

Claim: For all i > 2, if i is even then 2i + (2i-1 - 3) = 3*(2i-1 - 1) and if i is odd then 2i + (2i-1 + 3) = 3*(2i-1 + 1).

Proof by weak mathematical induction:

Base Case: i = 3

 23 + (23-1 + 3) = 8 + (4 + 3) = 15
 3*(23-1 + 1) = 3*(4+1) = 15            Clearly, base case holds

Inductive Step:

Suppose that 2i + (2i-1 + 3) = 3*(2i-1 + 1) is true for an odd i, must show that the claim is also true for the next odd i, namely i + 2.

Since 2i + (2i-1 + 3) = 3*(2i-1 + 1) then 2i  3*(2i-1 + 1) - (2i-1 + 3) 

Replacing i with i+2 yields

2i + 2 = 3*(2i +2 - 1 +  1) - ( 2i + 2 - 1 + 3)
2i + 2 = 3*2i+1  + 3 -  2i+1  - 3
2i + 2 = 3*2i+1  + 0 -  2i+1
2i + 2 = 2*2i+1   = 2i + 2

Similarly, suppose that 2i + (2i-1 - 3) = 3*(2i-1 - 1) is true for an even i, must show that the claim is also true for the next even i, namely i + 2

Replacing i with i+2 yields

2i + 2 = 3*(2i +2 - 1 -  1) - ( 2i + 2 - 1 - 3)
2i + 2 = 3*2i+1  - 3 -  2i+1  + 3                  
2i + 2 = 3*2i+1  - 0 -  2i+1
2i + 2 = 2*2i+1   = 2i + 2


A Shrewd Sequence

In previous entries I categorized integers n between 2i and 2i+1 where the order of 2 mod n has a common formula for each i.

For example:
1. I proved that if n is a Mersenne number (an integer of the form 2i - 1), then the order of 2 mod n is equal to i.

2. Then I conjectured that if n is of the form 2+ 1 then the order of 2 mod n is equal to 2*i.

3. I also conjectured that if n is of the form:

2i + (2(i-1) - 3) if i is even 
or 2i + (2i-1 + 3) if i is odd

or in other words of the form (here's the proof that these two formulas are equal)

3*(2i-1 - 1) if i is even
3*(2i-1 + 1) if i is odd 

then the order of 2 mod n is i + (i - 2)

Another example that I have not previously published on this blog is also based on just a conjecture that may turn out to be false.

Conjecture: For each i > 3 there exists at least one integer n such that 2< n < 2i+1 and the order of 2 mod n is equal to (i-1)*(i-2)

Below is a sequence generated using the first occurrence of such integers between 2i and 2i+1 for each i > 3

21, 35, 75, 231, 301, 731, 1241, 2079, 7513, 8337, 16485, 39173, 66591, 131241, 371365, 539973, 1125441, 2153525,...

Below is a slow calculator for finding the order of 2 mod n for any odd integer n:


Wiener Werkstaette Kunstlerinnen

Unlike some other museums, most museums allow people to take pictures of exhibits, and to spread the word about them to other potential visitors.

Paintings by Greta Wolf-Krakauer (1890 - 1970)

I visited Vienna, Austria in November of 2016. Vienna is one of the most beautiful cities in the world.

Vienna was home to many artists, writers, musicians, and philosophers at one point or another such as Franz Kafka, Mozart, Goethe, Stefan Zweig, and Freud. It was also home to a large partisan movement. Viennese partisans helped some Jewish families relocate to safety during World War II.

I went to J├╝disches Museum Wien to see an art exhibit titled "Das bessere Haelfte: Judische Kunstlerinen bis 1938", which celebrates the contribution of Jewish female artists to the development of Viennese modernism.

The exhibit blends together the works of well established Viennese artists with the works of the unfairly forgotten ones.

One of the artist featured in the exhibit is Friedl Dicker, who was born in Vienna in 1898 into a poor Jewish family. In 1915 Dicker joined the textile department of the School of Art and Crafts in Vienna.  
In 1919 she went to Weimar Bauhaus to study. She returned to Vienna four years later where she established a furniture atelier, which received awards at several exhibitions.

The photo below depicts a reproduction based on a collage by Friedl Dicker entitled "The Bourgeoisie Becomes Fascist" originally made in 1932.

Everyone can be an artist but not every artist can be a visionary. Friedl Dicker was a visionary.

In the above piece she managed to capture the spirit of the problem, which 10 years later nearly destroyed Europe, like no other artist before or after her.

Modern art played a central role in World War II. The Nazis felt threatened by it to such an extent that they organized a propaganda exhibit where popular modernist works were derided. Psychologists such as Carl Jung,  who enjoyed a blossoming career during the Nazi regime, and whose pseudo-scientific ramblings still corrode the popular Western culture today, saw modern art as a symbol of "corrosive character".  According to letters written by Jung during the Nazi regime in Germany, he was a Nazi sympathizer, yet he denied being a Nazi sympathizer after Nazi Germany lost WWII.

Meanwhile, Friedl Dicker had the option to flee Nazi Europe shortly before she was sent to a concentration camp but she chose to stay with those who couldn't go anywhere and tried to lift their spirits with art workshops where they drew flowers and landscapes to escape their gruesome reality. In 1944 she was gassed in Auschwitz along with some of her students.


Multiple Positions

Previously, I generated a sequence using the following recurrence relation and I made a few conjectures about it.

2i + (2(i-1) - 3) if i is even 
or 2i + (2i-1 + 3) if i is odd

I also wrote an algorithm based on this recurrence relation to generate the first few such integers up to some limit. The first 20 terms of the sequence with initial term i = 3 are:

Obviously, each term in this sequence is divisible by 1 or more primes.

Claim: If a term in this sequence at position b is divisible by a prime p then the term at position
b + (p-1)  is divisible by p.

This claim holds for all other recurrence relations of the form

2i + (2(i-1) - k) if i is even 
or 2i + (2i-1 + k) if i is odd

where k is any odd integer

It is easy to see it because it is a result of the fundamental theorem of algebra in that every integer can be represented as a product of primes.

For example, the first 20 terms of the sequence generated with the recurrence relation

2i + (2(i-1) - 7) if i is even 
or 2i + (2i-1 + 7) if i is odd


The first term 17 is a prime at position 0, and the term at position 0 + (17 - 1) = 16 is divisible by 17.
In fact 1572857/17 = 92521.

Similarly, 55 = 11* 5 is at position 1, so the term in the sequence at position 1 + (11 - 1) = 11 is divisible by 11 and the term at 1 + (5 - 1) = 5 is divisible by 5.

I'm willing to bet that the 90th term in the sequence is divisible by 89 and the 201st term is divisible by 199.

377 = 13*29 is at position 4 in the sequence and the term in the sequence that's at position 4+(13-1) = 16 is 1572857, which is divisible by 13. In fact, the term at position 4+(29-1) = 32 is 103079215097 and it is divisible by 29 among other integers.

And so on.

One of the claims I made for the sequence where k = 3 is that every single element in it is divisible by 3. It is also easy to see why this is so using the claim above since the first 2 terms of the sequence at position 0 and 1 respectively are divisible by 3. Namely, if the initial i = 3 then clearly the first term of the sequence at position 0 is 23 + (22 - 3) = 15, which is divisible by 3 so the term at position 0+(3-1) = 2 will also be divisible by 3. Therefore, every second term will be divisible by 3. To calculate the term at position 1, I plug in i = 4 so 24+ (23 - 3) = 21, which is also divisible by 3 so every third element of the sequence will also be divisible by 3. 

Similarly, if k is equal to any other odd multiple of 3, then the sequence generated using the relation

2i + (2(i-1) - k) if i is even 
or 2i + (2i-1 + k) if i is odd

is composed of terms such that every term is divisible by 3.

I also made another claim related to the sequence when k = 3. I claimed that for each term n where

n = 2i + (2(i-1) - 3) if i is even 
or n = 2i + (2i-1 + 3) if i is odd

the order of 2 mod n is i+(i-2) 

I haven't been able to see why this is the case yet but it holds for the first 50 terms of the sequence, and beyond as far as I can see.

Below is a graphic I made of different sequences generated for different k with initial i = 4.

The interesting thing about this is that only the sequence for k = 1 exists in the OEIS.org database of sequences but it is generated using a different relation, and the sequence itself is an amalgamation of sequences concerning powers of 3.

Neither of the other sequences I presented here have found their way into the OEIS.org database of integer sequences.