Compute The Private Rsa Key To Decrypt The Given Messenger

카테고리 없음

by saisublenfun1978 2020. 11. 9. 11:35

Using Rsa Key To Login
Compute The Private Rsa Key To Decrypt The Given Messenger Online

RSA

In 1978, Rivest, Shamir and Adleman of MIT proposed anumber-theoretic way of implementing a Public Key Cryptosystem. Their methodhas been widely adopted. The basic technique is:

Choose two large prime numbers, p and q.
compute n = p * q and x = (p-1)*(q-1)
Choose a number relatively prime to x and call it d. This means that d is not a prime factor of x or a multiple of it.
Find e such that e * d = 1 mod x.

This is (hopefully) a very simple example of how to calculate RSA public and private keys. Just to be clear: these values should not be used for any real encryption purposes.

To use this technique, divide the plaintext (regarded as a bit string) intoblocks so that each plaintext message P falls into the interval .This can be done by dividing it into blocks of k bits where is thelargest integer for which 2^k < nis true.

To encrypt: C
To decrypt: P

The public key, used to encrypt, is thus: andthe private key, used to decrypt, is (d, n))

RSA Example -- Key Generation

To create the public key, select two large positive prime numbers `p` and `q`	`p` `= 7, q = 17` Large enough for us!
Compute `(p-1) * (q-1)`	`x` `= 96`
Choose an integer `E` which is relatively prime to `x`	`E` `= 5`
Compute `n` `= p * q`	`n` `= 119`
`K_p` is then `n` concatenated with `E`	`K_p` `= 119, 5`

To create the secret key, compute D such that (D * E) mod x = 1

K_s = 119, 77

RSA Example -- Encryption and Decryption

To compute the ciphertext `C` of plaintext `P`, treat `P` as a numerical value	`P` `= 19`
`C` `= P^E mod n`	`C` `= 66`

To compute the plaintext `P` from ciphertext `C`:
`P` `= C^D mod n`	`P` `= 19`

RSA in Practice

RSA works because knowledge of the public key does notreveal the private key. Note that both the public and private keys contain theimportant number n = p * q.The security of the system relies on the fact that is hard to factor-- that is, given a large number (even one which is known to have only twoprime factors) there is no easy way to discover what they are. This is a wellknown mathematical fact. If a fast method of factorisation is everdiscovered then RSA will cease to be useful.

It is obviously possible to break RSA with a bruteforce attack -- simply factorise n. To make this difficult, it'susually recommended that p and q be chosen so that is (in2002 numbers) at least 1024 bits.

One excellent feature of RSA is that it is symmetrical.We already know that if you encrypt a message with my public key then only Ican decrypt that ciphertext, using my secret key. However, it also turns outthat a message encrypted with my secret key can only be decrypted withmy public key. This has important implications, see later.

The RSA algorithm operates with huge numbers, and involves lots ofexponentiation (ie, repeated multiplication) and modulus arithmetic. Suchoperations are computationally expensive (ie, they take a longtime!) and so RSA encryption and decryption are incredibly slow,even on fast computers. Compare this to theoperations involved in DES (and other single-key systems)which consist of repeated simple XORsand transpositions. Typical numbers are that DES is 100 times faster than RSAon equivalent hardware. Furthermore, DES can be easily implemented in dedicatedhardware (RSA is, generally speaking, a software-only technology) giving aspeed improvement of up to 10,000 times.

Public Key Cryptography In Summary

A public key is used to encrypt and a separate, different private key to decrypt the message.
Each party involved generates a key pair.
Each party publishes their public key. This is made widely known to all potential communication partners.
Each party secures their private key, which must remain secret.
Assuming A desires to send a message to B, A first encrypts the message using B's public key.
B can decrypt the message using its private key. Since no one else knows B's private key, this is absolutely secure -- no one else can decrypt it.
There still remain difficult problems of authentication of public keys, compromised keys, bogus & out of date keys. Further, Public Key encryption is very, very slow compared to single key systems.
A very useful and common way of using public key cryptography is as a means of establishing/distributing secret keys for conventional single key cryptography, see later.

In cryptography, RSA (which stands for Rivest, Shamir and Adleman who first publicly described it) is an algorithm for public-key cryptography. It is the first algorithm known to be suitable for signing as well as encryption, and was one of the first great advances in public key cryptography. RSA is widely used in electronic commerce protocols, and is believed to be sufficiently secure given sufficiently long keys and the use of up-to-date implementations.

Java Code Examples

RPGLE iSeries Code Examples

Public-key cryptography refers to a cryptographic system requiring two separate keys, one to lock or encrypt the plaintext, and one to unlock or decrypt the cyphertext. Neither key will do both functions. One of these keys is published or public and the other is kept private. If the lock/encryption key is the one published then the system enables private communication from the public to the unlocking key's owner.

How does Public-Key encryption work?

Let's assume we have two parties, Bob and Alice, who wish to transmit confidential information to one another over the Internet. Alice would like to send Bob a corporate document using a Public Key encryption system. To accomplish a secure transmission, they will need to do the following :

Alice and Bob agree on a public-key cryptosystem.
Bob generates a pair of mathematically linked keys : one public, one private.
Bob transmits his public key to Alice over any insecure medium.
Bob keeps the private key a secret.
Alice uses Bob's public key and the encryption algorithm to encrypt her message, creating a ciphertext.
Alice transmits the ciphertext to Bob.
Bob decrypts the ciphertext using the same algorithm and his private key.

The Bouncy Castle Crypto APIs for Java consist of the following:

A lightweight cryptography API.
A provider for the Java Cryptography Extension and the Java Cryptography Architecture.
A clean room implementation of the JCE 1.2.1.
A library for reading and writing encoded ASN.1 objects.
A lightweight client-side TLS API.
Generators for Version 1 and Version 3 X.509 certificates, Version 2 CRLs, and PKCS12 files.
Generators for Version 2 X.509 attribute certificates.
Generators/Processors for S/MIME and CMS (PKCS7/RFC 3852).
Generators/Processors for OCSP (RFC 2560).
Generators/Processors for TSP (RFC 3161 & RFC 5544).
Generators/Processors for CMP and CRMF (RFC 4210 & RFC 4211).
Generators/Processors for OpenPGP (RFC 2440).
A signed jar version suitable for JDK 1.4-1.6 and the Sun JCE.

The lightweight API works with everything from the J2ME to the JDK 1.6.

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:

Choose two distinct prime numbers p and q.

For security purposes, the integers p and q should be chosen at random, and should be of similar bit-length. Prime integers can be efficiently found using a primality test.

Compute n = pq.

n is used as the modulus for both the public and private keys

Compute φ(n) = (p – 1)(q – 1), where φ is Euler's totient function.
Choose an integer e such that 1 < e < φ(n) and gcd(e,φ(n)) = 1, i.e. e and φ(n) are coprime.

e is released as the public key exponent.
e having a short bit-length and small Hamming weight results in more efficient encryption - most commonly 0x10001 = 65537. However, small values of e (such as 3) have been shown to be less secure in some settings.[4]

Determine d = e^–1 mod φ(n); i.e. d is the multiplicative inverse of e mod φ(n).

This is more clearly stated as solve for d given (d*e)mod φ(n) = 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 private (or decryption) exponent d which must be kept secret.

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 m, such that 0 < m < n by using an agreed-upon reversible protocol known as a padding scheme. He then computes the ciphertext c corresponding to
c = m^e (mod n).
This can be done quickly using the method of exponentiation by squaring. Bob then transmits c to Alice.