If n is the product of two distinct odd primes p and q, then there are 4 square roots for each squared integer a such that GCD(a,n) = 1. There appears to be a relationship between the smallest square root of ((n+1)/2)^2 (mod n) and a multiple of p or q.

Conjecture 1.: Let n be the product of two distinct odd primes p and q. If s is the smallest square root of ((n+1)/2)^2 (mod n) then (n+1)/2 - s = rp such that GCD(rp, n) = p

Empirical evidence suggests that this conjecture holds for any n as long as n is the product of two distinct primes. In fact, the following algorithm can be used to factor n.

1. Calculate k = ((n+1)/2)^2 (mod n)

2. Find the smallest square root s of k mod n

3. Calculate xp = (n+1)/2 - s

4. Return GCD(xp, n)

Example:

a. Let n = 35

1. k = 18^2 (mod 35) = 9

2. s = sqrt(9) = 3

3. xp = 18 - 3 = 15

4. GCD (15, 35) = 5

Step #2 can be further divided into two cases. The first case relates to k being a perfect square. If k is a perfect square then there is no need to use modular arithmetic to calculate the smallest square root of k. All known algorithms for computing the square root of a perfect square in Z will return the smallest square root of k. However, if k is not a perfect square in Z then finding its square root in Z_n becomes a different problem altogether.

# The Bad Byte

## 4.1.18

## 27.12.17

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

**Example:**

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

Labels:
Euler's Phi Function
,
Mathematics
,
RSA Problem
,
safe primes

## 3.12.17

### 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 d

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.

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 d

_{1}is the intended private key and (n, e) is the public key then the second key d_{2}can be found using the following formula:
d

_{2}*e = phi(n)/2Here'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.

## 4.9.17

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

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.

*to be defined in future blog posts

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

Labels:
Euler's Phi Function
,
Euler's Totient Function
,
exponent
,
Mathematics

## 30.8.17

### 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

**Example:**

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

## 25.7.17

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

Conjecture 1: Given p a steady prime and a < p such that it is not a power of 2 mod p then

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

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

Labels:
Mathematics
,
safe primes
,
steady primes
,
tough primes

## 13.6.17

## 2.6.17

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

## 26.4.17

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

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:

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

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 Z

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.

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

**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)/2In 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 Z_{11}and Z_{7}.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 Z

_{7}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.

Labels:
Mathematics
,
Order of An Element
,
RSA Problem
,
safe primes
,
steady primes
,
tough primes

## 20.4.17

### Why Steady Primes?

In my previous entry I discussed a subset of safe primes with an interesting property.

It appears that when a prime p is of the form 8k - 1 where 4k - 1 and 8k - 1 are both primes, then the order of each power of 2 mod p is phi(p)/2 where phi() is the Euler's Totient Function.

This is only one part of my conjecture. Here's another part of it:

In my previous entry I called such primes "steady primes". The reason why I chose the name "steady" is because of the "steady", uniform structure of the exponentiation table of Z

All elements of Z

Example: The first few steady primes are: 7,23,47,167,263,359,383,479,503

phi(p)/2 when p is the first few steady primes is equal to: 3,11, 23, 83, 131, 179, 191, 239, 261

Unfortunately, the curious properties of steady primes are not applicable to all products of steady primes. There are some products of steady primes pq with such uniform structure of the exponentiation table of Z

Below is a calculator that can be used to generate powers of powers of integers modulo other integers, the algorithm for which I described here.

It appears that when a prime p is of the form 8k - 1 where 4k - 1 and 8k - 1 are both primes, then the order of each power of 2 mod p is phi(p)/2 where phi() is the Euler's Totient Function.

This is only one part of my conjecture. Here's another part of it:

**Conjecture:**If p is a prime of the form 8k - 1 where 4k - 1 and 8k - 1 are both primes and n is an integer smaller than q such that it is not a power of 2 mod p, then the order of n mod p is phi(p)= p-1**Example:**Below is an image of the exponentiation tables of Z_{23}and Z_{7}.In my previous entry I called such primes "steady primes". The reason why I chose the name "steady" is because of the "steady", uniform structure of the exponentiation table of Z

_{p}when p is a steady prime.All elements of Z

_{p}when p is a steady prime have order that is equal to or greater than phi(p)/2. This is also true for the rest of the safe primes, which are the tough primes, but the structure of the exponentiation table of Z_{p}when p is a tough prime is different. With tough primes every odd power of 2 mod p has order p-1 and every even power of 2 mod p has order phi(p)/2.**Conjecture:**If p is a steady prime, then phi(p)/2 is also a prime number.Example: The first few steady primes are: 7,23,47,167,263,359,383,479,503

phi(p)/2 when p is the first few steady primes is equal to: 3,11, 23, 83, 131, 179, 191, 239, 261

Unfortunately, the curious properties of steady primes are not applicable to all products of steady primes. There are some products of steady primes pq with such uniform structure of the exponentiation table of Z

_{pq}but they are kind of rare.Below is a calculator that can be used to generate powers of powers of integers modulo other integers, the algorithm for which I described here.

Labels:
Euler's Phi Function
,
Euler's Totient Function
,
Mathematics
,
steady primes
,
tough primes

Subscribe to:
Posts
(
Atom
)