What's new

# Discussion A little lesson on RSA

#### joshandrok

##### Enthusiast
I have been seeing alot of talk about altering mp.ff files in MW2. And then I see people say "I have it decrypted" and such. But apparently some people don't understand what an RSA Signature is. This text will be long, but it's a good read(hopefully), and maybe all you future modders can understand just how this RSA thing works. So lets get started. . .
So lets look at the chances of one single person ever figuring out the full key.

"Clearly, a pivotal issue in hacking the Xbox console is their implementaion of the digital signature system.
The Xbox uses a SHA-1 hash with 2048-bit RSA keys, making the chance of a successful brute force attack very, very slim.
Of course, the probablility is zero if you never try, but the odds are stacked against you.
You'll have better luck trying to win the lottery.
This is by no mistake; the discovery of the private key would make game copying trivial and developers would not have to pay royalties to Microsoft.
Given that this key is probably worth a few billion dollars to Microsoft, it is quite likely that no single human knows the full key, as rubber hose, and green-paper cryptanalysis techniques tend to be quite effective on humans."

So now lets look at the algorithm behind an RSA signature.

"1. Find two large(thousands of bits long) prime numbers. "P" and "Q".
2. Choose "E" such that E>1,E<PQ and E is relatively prime to (P-1)(Q-1).
E does not have to be prime, bit it must add. The pair of E and PQ are the public key.
3. Compute "D" suck that (DE - 1) is evenly divislbe by (P-1)(Q-1).
This can be accomplished by finding an integer. D is the private key.
4. Plaintext "T" is encrypted using the function C=(T) mod PQ
5. Ciphertext "C" is decrypted using the function T=(C) mod PQ

Note that T<PQ messages larger than PQ must be broken down into a sequence of smaller messages,
and very shot messages must be padded with carefully selected values to foil dictionary attacks among other things. "

So what does this mean for modders

"In the Xbox, digital signatures are used to control the
distribution and sale of programs for the console.
Microsoft is effectively in control of both the sender
and the reciever of messages.
The receivers- Xbox console - are programmed to only run programs
that are digital signed by Microsoft. In an Ideal world, this
guarantees that Microsoft has the final word
on who or who cannot run programs on the console, and hackers cannot
modify games to insert viruses, Trojan horses, or back doors.
Saved games are also sealed using encryptions, and as a result,
it is nominally impossible to hack a game and cheat by patching
the executable or by jacking up your character stats."

This is basically saying that we are not getting into anything that is signed with RSA.
Now I am by no means a hardcore 1337 haxzorz. In fact I have hardly even begun to understand the whole RSA thing. I just know that if it is signed with it, then you might as well give up. I just posted this because I'm tired of seeing all these threads about modding the mp.ff files to play online mods for MW2. It's just simply not logical to waste time on it. But whatever, To each his own. If you still feel that you should go about modding online MW2 via the ISO, then go for it, but I doubt you get anywhere seeing as how people have been working on Microsoft's RSA key for years. I hope this shed some light on RSA signatures for some of you. It definitely helped me. . .
This all was taken from the book "Hacking the Xbox: An Introduction to Reverse Engineering.

Sorry Unknown v2, I didn't see your thread. I was typing this one while you were posting yours lol. .

#### CraigChrist8239

##### VIP
VIP
joshandrok said:
So lets look at the chances of one single person ever figuring out the full key.

making the chance of a successful brute force attack very, very slim. Of course, the probablility is zero if you never try, but the odds are stacked against you. You'll have better luck trying to win the lottery.
All I got out of that was that is was possible, yet very very hard. Whos to say it hasn't been done already?

#### joshandrok

##### Enthusiast
craigchrist8239 said:
All I got out of that was that is was possible, yet very very hard. Whos to say it hasn't been done already?
I never said it hasn't been done.

VIP
It hasn't.

#### joshandrok

##### Enthusiast
Luckily I never said it has either lol

#### KN1GHTH4WK429

##### Enthusiast
The RSA algorithm involves three steps: key generation, encryption and decryption.
 Key generation

RSA involves a public key and a private key. The public key can be known to everyone and is used for encrypting messages. Messages encrypted with the public key can only be decrypted using the private key. The keys for the RSA algorithm are generated the following way:

1. Choose two distinct prime numbers p and q.
• For security purposes, the integers p and q should be chosen uniformly at random and should be of similar bit-length. Prime integers can be efficiently found using a primality test.
2. Compute n = pq.
• n is used as the modulus for both the public and private keys
3. Compute the totient: φ(pq) = (p − 1)(q − 1).
4. Choose an integer e such that 1 < e < φ(pq), and e and φ(pq) share no divisors other than 1 (i.e. e and φ(pq) are coprime).
• e is released as the public key exponent.
• Choosing e having a short addition chain results in more efficient encryption. Small public exponents (such as e = 3) could potentially lead to greater security risks.[2]
5. Determine d (using modular arithmetic) which satisfies the congruence relation
.
• Stated differently, ed − 1 can be evenly divided by the totient (p − 1)(q − 1).
• This is often computed using the extended Euclidean algorithm.
• d is kept as the private key exponent.
The public key consists of the modulus n and the public (or encryption) exponent e. The private key consists of the modulus n and the private (or decryption) exponent d which must be kept secret.
Notes on some variants:

• PKCS#1 v2.0 and PKCS#1 v2.1 specifies using
, where lcm is the least common multiple instead of
.
• For efficiency the following values may be precomputed and stored as part of the private key:
• p and q: the primes from the key generation,
• and
,
• .
 Encryption

Alice transmits her public key (n,e) to Bob and keeps the private key secret. Bob then wishes to send message M to Alice.
He first turns M into an integer 0 < m < n by using an agreed-upon reversible protocol known as a padding scheme. He then computes the ciphertext c corresponding to:
This can be done quickly using the method of exponentiation by squaring. Bob then transmits c to Alice.
 Decryption

Alice can recover m from c by using her private key exponent d by the following computation:
Given m, she can recover the original message M by reversing the padding scheme.
The above decryption procedure works because:
. Now, since
,
. The last congruence directly follows from Euler's theorem when m is relatively prime to n. It can be shown that the equations holds for all m using congruency arguments and the EEA.
This shows that we get the original message back:
 A working example

Here is an example of RSA encryption and decryption. The parameters used here are artificially small, but one can also use OpenSSL to generate and examine a real keypair.

1. Choose two prime numbers p = 61 and q = 53
2. Compute n = pq
3. Compute the product of totients. For primes said totient is maximal and invariably comes in at x − 1. Therefore
4. Choose e > 1 subject to it being coprime to 3120. Picking a prime number for e leaves you with a single check: that e be no divisor of 3120. e = 17
5. Compute d such that
e.g., by computing the modular multiplicative inverse of e modulo
: d = 2753since 17 2753 = 46801 and mod (46801,3120) = 1 this is the correct answer.(iterating finds (15 times 3120)+1 divided by 17 is 2753, an integer, whereas other values in place of 15 do not produce an integer)

The public key is (n = 3233, e = 17). For a padded message m the encryption function is
or abstractly:

The private key is (n = 3233, d = 2753). The decryption function is
or in its general form:

For instance, in order to encrypt m = 123, we calculate
To decrypt c = 855, we tap
. Both of these calculations can be computed efficiently using the square-and-multiply algorithm for modular exponentiation. In real life situations the primes selected would be much larger, however in our example it would be relatively trivial to factor n, 3233, obtained from the freely available public key back to the primes p and q. Given e, also from the public key, we could then compute d and so acquire the private key.
theres your tut on how to hack the RSA
unless your a math wiz or a computer programmer that implements this from scratch into your data base, server, ect, ect your F*cked

well happy hacking
and btw this is calculus D-F(college level classes for computer programmers and such)
so unless you mastered that or are in the process of learning it or have a computer programmer who will help you decrypt it its near impossible

#### Lost4468

##### Contributor
It is possible to decrypt as the public key is in the xex.

editut private -.-

#### SotG Caboose

##### Getting There
KN1GHTH4WK429 said:
theres your tut on how to hack the RSA
unless your a math wiz or a computer programmer that implements this from scratch into your data base, server, ect, ect your F*cked

well happy hacking
and btw this is calculus D-F(college level classes for computer programmers and such)
so unless you mastered that or are in the process of learning it or have a computer programmer who will help you decrypt it its near impossible

RSA - Wikipedia, the free encyclopedia link i forgot
Why do you keep posting this? You obviously don't understand how it works either. Anyone can decrypt, as it stores the public key in the .xex. It needs to verify the hash. We just can't encrypt because the private key is only used once, and It isn't stored anywhere except the game studio the file was created in.

#### unknown v2

##### VIP
VIP
The only key in the xex is the public key, which I've extracted and there is in fact no private key in the xex (would ruin the whole point of an RSA signature).

#### KN1GHTH4WK429

##### Enthusiast
its this simple you decrypt the public key you get the private key
only the private key can decrypt the public key so in general if you have thought about it you would know this would work but what ever
****ing me generation think they know everything
if you would have read the whole post you would have seen that
The public key consists of the modulus n and the public (or encryption) exponent e. The private key consists of the modulus n and the private (or decryption) exponent d
so we have the private key why not just decrypt the public key using the algorithm above and find out what variable d is instead of flaming me you could try to work on it
i gave you the knowledge to decrypt it so why not use that
its algebra from this point
god you me generation need to read the whole damn post next time

#### EclipseModz

##### VIP
VIP
Retired
KN1GHTH4WK429 said:
its this simple you decrypt the public key you get the private key
only the private key can decrypt the public key so in general if you have thought about it you would know this would work but what ever
****ing me generation think they know everything
if you would have read the whole post you would have seen that

so we have the private key why not just decrypt the public key using the algorithm above and find out what variable d is instead of flaming me you could try to work on it
i gave you the knowledge to decrypt it so why not use that
its algebra from this point
god you me generation need to read the whole damn post next time
If its so simple. Then why don't you do it? Hmm..? Or are you only able to copy and paste?

#### unknown v2

##### VIP
VIP
its this simple you decrypt the public key you get the private key
only the private key can decrypt the public key
I can't believe how stupid you are.

#### joshandrok

##### Enthusiast
KN1GHTH4WK429 said:
its this simple you decrypt the public key you get the private key
only the private key can decrypt the public key so in general if you have thought about it you would know this would work but what ever
****ing me generation think they know everything
if you would have read the whole post you would have seen that

so we have the private key why not just decrypt the public key using the algorithm above and find out what variable d is instead of flaming me you could try to work on it
i gave you the knowledge to decrypt it so why not use that
its algebra from this point
god you me generation need to read the whole damn post next time
Do you not understand what Unknown and Caboose said? WE DO NOT HAVE THE PRIVATE KEY. That's why it's called the PRIVATE KEY. Caboose said that the private key is only used once and is stored in the dev teams studio. Unknown said that he has been through the xex and the only key is the public key. So now if you would read your own post you would see that it says the encrypted public keys can only be decrypted with the private keys, which WE DO NOT HAVE... This is why Microsoft uses this system. Basically what everyone is saying; is your formula only works if you have both the Public and Private keys. And from what I have read so far, the RSA key is thousands of bytes long, and not one single human being knows the whole thing. So if you think that this formula can solve something that Microsoft is obviously keeping top secret then you're crazy.

#### KN1GHTH4WK429

##### Enthusiast
joshandrok said:
Do you not understand what Unknown and Caboose said? WE DO NOT HAVE THE PRIVATE KEY. That's why it's called the PRIVATE KEY. Caboose said that the private key is only used once and is stored in the dev teams studio. Unknown said that he has been through the xex and the only key is the public key. So now if you would read your own post you would see that it says the encrypted public keys can only be decrypted with the private keys, which WE DO NOT HAVE... This is why Microsoft uses this system. Basically what everyone is saying; is your formula only works if you have both the Public and Private keys. And from what I have read so far, the RSA key is thousands of bytes long, and not one single human being knows the whole thing. So if you think that this formula can solve something that Microsoft is obviously keeping top secret then you're crazy.
we have the DAMN PUBLIC KEY and the private key decrypts the public key
so we decrypt the public key it means now we have the private key
GOD DAMN
and you would decrypt it by USING THE DAMN ALGORITHM IN MY POST ABOVE
YA IT WILL TAKE A WHILE BUT HELL IT WILL WORK
you dont have variable d
so what do you do
you solve for d
it than becomes like algebra and you solve for the missing varable

#### SotG Caboose

##### Getting There
The keys are not encrypted. >______>

#### unknown v2

##### VIP
VIP
KN1GHTH4WK429 said:
the private key decrypts the public key
so we decrypt the public key it means now we have the private key

#### Doeboy1337

##### Member
KN1GHTH4WK429 said:
we have the DAMN PUBLIC KEY and the private key decrypts the public key
so we decrypt the public key it means now we have the private key
GOD DAMN
and you would decrypt it by USING THE DAMN ALGORITHM IN MY POST ABOVE
YA IT WILL TAKE A WHILE BUT HELL IT WILL WORK
you dont have variable d
so what do you do
you solve for d
it than becomes like algebra and you solve for the missing varable
why must you hit enter after every sentence. is your . button broke?

#### joshandrok

##### Enthusiast
KN1GHTH4WK429 said:
we have the DAMN PUBLIC KEY and the private key decrypts the public key
so we decrypt the public key it means now we have the private key
GOD DAMN
and you would decrypt it by USING THE DAMN ALGORITHM IN MY POST ABOVE
YA IT WILL TAKE A WHILE BUT HELL IT WILL WORK
you dont have variable d
so what do you do
you solve for d
it than becomes like algebra and you solve for the missing varable
Dude, you obviously don't understand. The Public and Private keys are not encrypted files. . . The public key or (n, e) is used to encrypt a message. The Private key (n, d) is then used to decrypt the message. That's just an encryption method. That is not an algorithm to figure out the private key. You can't figure out the private key just because you have the public key. If that were possible then the whole system would be flawed and people would not be using this method.
Then you have digital signing.
A message is created, the private key (n, d) is now used to create a signature.
Now the message has been sent and received. The public key (n, e) is now used to extract the message. Now if both messages are identical that means they have not been tampered with and it is a valid signature. . .
Now do you understand where we have problems. I don't think anyone cares about encryption and decryption. We can't sign the damn thing to verify. And we need the private key to sign it. And there is NO algorithm to figure out the private key. The private key is a secret. That's the whole point of RSA signing. . .

#### KN1GHTH4WK429

##### Enthusiast
joshandrok said:
Dude, you obviously don't understand. The Public and Private keys are not encrypted files. . . The public key or (n, e) is used to encrypt a message. The Private key (n, d) is then used to decrypt the message. That's just an encryption method. That is not an algorithm to figure out the private key. You can't figure out the private key just because you have the public key. If that were possible then the whole system would be flawed and people would not be using this method.
Then you have digital signing.
A message is created, the private key (n, d) is now used to create a signature.
Now the message has been sent and received. The public key (n, e) is now used to extract the message. Now if both messages are identical that means they have not been tampered with and it is a valid signature. . .
Now do you understand where we have problems. I don't think anyone cares about encryption and decryption. We can't sign the damn thing to verify. And we need the private key to sign it. And there is NO algorithm to figure out the private key. The private key is a secret. That's the whole point of RSA signing. . .
RSA - Wikipedia, the free encyclopedia

read the damn article cause if the RSA wasnt a form of encryption than idk what is
god damn

Encryption

Alice transmits her public key (n,e) to Bob and keeps the private key secret. Bob then wishes to send message M to Alice.
He first turns M into an integer 0 < m < n by using an agreed-upon reversible protocol known as a padding scheme. He then computes the ciphertext c corresponding to:
This can be done quickly using the method of exponentiation by squaring. Bob then transmits c to Alice.
 Decryption

Alice can recover m from c by using her private key exponent d by the following computation:
Given m, she can recover the original message M by reversing the padding scheme.
The above decryption procedure works because:
. Now, since
,
. The last congruence directly follows from Euler's theorem when m is relatively prime to n. It can be shown that the equations holds for all m using congruency arguments and the EEA.
This shows that we get the original message back:
 A working example

Here is an example of RSA encryption and decryption. The parameters used here are artificially small, but one can also use OpenSSL to generate and examine a real keypair.

1. Choose two prime numbers p = 61 and q = 53
2. Compute n = pq
3. Compute the product of totients. For primes said totient is maximal and invariably comes in at x − 1. Therefore
4. Choose e > 1 subject to it being coprime to 3120. Picking a prime number for e leaves you with a single check: that e be no divisor of 3120. e = 17
5. Compute d such that
e.g., by computing the modular multiplicative inverse of e modulo
: d = 2753since 17 2753 = 46801 and mod (46801,3120) = 1 this is the correct answer.(iterating finds (15 times 3120)+1 divided by 17 is 2753, an integer, whereas other values in place of 15 do not produce an integer)

The public key is (n = 3233, e = 17). For a padded message m the encryption function is
or abstractly:

The private key is (n = 3233, d = 2753). The decryption function is
or in its general form:

For instance, in order to encrypt m = 123, we calculate
To decrypt c = 855, we tap
. Both of these calculations can be computed efficiently using the square-and-multiply algorithm for modular exponentiation. In real life situations the primes selected would be much larger, however in our example it would be relatively trivial to factor n, 3233, obtained from the freely available public key back to the primes p and q. Given e, also from the public key, we could then compute d and so acquire the private key.
it explains how RSA is used to encrypt files and how it is decrypted
and if you clearly look above there is algorithm behind the RSA signature
so really wheres your proof saying that there is no algorithm behind RSA

and to GAIN THE PRIVATE KEYS you would reverse the encryption method so find out what d is
heres a simple example for you guys who dont understand

5 = d+e
e = 9
5 = d+9
d = -4

we have the e variable so all we have to do is solve for d
its not going to be simple but it WILL WORK ok i am in calculus but i really dont understand any of this
so someone who is smarter than me will have to work this out cause i understand about 5% of this

http://www.ietf.org/rfc/rfc4432.txt
theres an introduction article to RSA