# RSA Encryption

Question asked by 4M4N in #Hacking and Security on Dec 27, 2010

4M4N · Dec 27, 2010

Rank C3 - EXPERT

One commonly used cipher of this forms called RSA Encryption,

where RSA are the initials of the three creators: Rivest, Shamir, and Adleman. It

is based on the following idea:

It is very simply to multiply numbers together, especially with computers. But it can

be very difficult to factor numbers. For example, if I ask you to multiply together

34537 and 99991, it is a simple matter to punch those numbers into a calculator and

3453389167. But the reverse problem is much harder.

Suppose I give you the number 1459160519. I'll even tell you that I got it by multi-

plying together two integers. Can you tell me what they are? This is a very difficult

problem. A computer can factor that number fairly quickly, but (although there are

some tricks) it basically does it by trying most of the possible combinations. For any

size number, the computer has to check something that is of the order of the size of

the square-root of the number to be factored. In this case, that square-root is roughly

38000.

Now it doesn't take a computer long to try out 38000 possibilities, but what if the

number to be factored is not ten digits, but rather 400 digits? The square-root of a

number with 400 digits is a number with 200 digits. The lifetime of the universe is

approximately 10^18 seconds an 18 digit number. Assuming a computer could test

one million factorizations per second, in the lifetime of the universe it could check

10^24 possibilities. But for a 400 digit product, there are 10^200 possibilties. This means

the computer would have to run for 10^176 times the life of the universe to factor the

large number.

It is, however, not too hard to check to see if a number is prime in other words to

check to see that it cannot be factored. If it is not prime, it is difficult to factor, but if it

is prime, it is not hard to show it is prime.

So RSA encryption works like this. I will find two huge prime numbers, p and q that

have 100 or maybe 200 digits each. I will keep those two numbers secret (they are

my private key), and I will multiply them together to make a number N = pq. That

number N is basically my public key. It is relatively easy for me to get N; I just need

to multiply my two numbers. But if you know N, it is basically impossible for you

to find p and q. To get them, you need to factor N, which seems to be an incredibly

difficult problem.

But exactly how is N used to encode a message, and how are p and q used to decode

it? Below is presented a complete example, but I will use tiny prime numbers so it is

easy to follow the arithmetic. In a real RSA encryption system, keep in mind that the

prime numbers are huge. Posted in: #Hacking and Security

where RSA are the initials of the three creators: Rivest, Shamir, and Adleman. It

is based on the following idea:

It is very simply to multiply numbers together, especially with computers. But it can

be very difficult to factor numbers. For example, if I ask you to multiply together

34537 and 99991, it is a simple matter to punch those numbers into a calculator and

3453389167. But the reverse problem is much harder.

Suppose I give you the number 1459160519. I'll even tell you that I got it by multi-

plying together two integers. Can you tell me what they are? This is a very difficult

problem. A computer can factor that number fairly quickly, but (although there are

some tricks) it basically does it by trying most of the possible combinations. For any

size number, the computer has to check something that is of the order of the size of

the square-root of the number to be factored. In this case, that square-root is roughly

38000.

Now it doesn't take a computer long to try out 38000 possibilities, but what if the

number to be factored is not ten digits, but rather 400 digits? The square-root of a

number with 400 digits is a number with 200 digits. The lifetime of the universe is

approximately 10^18 seconds an 18 digit number. Assuming a computer could test

one million factorizations per second, in the lifetime of the universe it could check

10^24 possibilities. But for a 400 digit product, there are 10^200 possibilties. This means

the computer would have to run for 10^176 times the life of the universe to factor the

large number.

It is, however, not too hard to check to see if a number is prime in other words to

check to see that it cannot be factored. If it is not prime, it is difficult to factor, but if it

is prime, it is not hard to show it is prime.

So RSA encryption works like this. I will find two huge prime numbers, p and q that

have 100 or maybe 200 digits each. I will keep those two numbers secret (they are

my private key), and I will multiply them together to make a number N = pq. That

number N is basically my public key. It is relatively easy for me to get N; I just need

to multiply my two numbers. But if you know N, it is basically impossible for you

to find p and q. To get them, you need to factor N, which seems to be an incredibly

difficult problem.

But exactly how is N used to encode a message, and how are p and q used to decode

it? Below is presented a complete example, but I will use tiny prime numbers so it is

easy to follow the arithmetic. In a real RSA encryption system, keep in mind that the

prime numbers are huge. Posted in: #Hacking and Security

Deepika Bansal · Dec 28, 2010

Rank B2 - LEADER

Very informative...

As you say, N is the public key and p is your private key. That means q is the private key of the other person or machine involved in the communication.

My doubt here is why is there need of two private keys and a public key. I mean the same process of encoding/decoding can be done using two private keys or a private + a public key.. Please explain me..

As you say, N is the public key and p is your private key. That means q is the private key of the other person or machine involved in the communication.

My doubt here is why is there need of two private keys and a public key. I mean the same process of encoding/decoding can be done using two private keys or a private + a public key.. Please explain me..

4M4N · Jan 9, 2011

Rank C3 - EXPERT

In RSA there exist digital signature schemes

Digital signature schemes can be used for sender authentication and non-repudiation. In such a scheme a user who wants to send a message computes a digital signature of this message and then sends this digital signature together with the message to the intended receiver. Digital signature schemes have the property that signatures can only be computed with the knowledge of a private key.

Digital signature schemes can be used for sender authentication and non-repudiation. In such a scheme a user who wants to send a message computes a digital signature of this message and then sends this digital signature together with the message to the intended receiver. Digital signature schemes have the property that signatures can only be computed with the knowledge of a private key.