RSA Algorithm Example

• Choose p = 3 and q = 11
• Compute n = p * q = 3 * 11 = 33
• Compute φ(n) = (p - 1) * (q - 1) = 2 * 10 = 20
• Choose e such that 1 < e < φ(n) and e and n are coprime. Let e = 7
• Compute a value for d such that (d * e) % φ(n) = 1. One solution is d = 3 [(3 * 7) % 20 = 1]
• Public key is (e, n) => (7, 33)
• Private key is (d, n) => (3, 33)
• The encryption of m = 2 is c = 2⁷ % 33 = 29
• The decryption of c = 29 is m = 29³ % 33 = 2

The RSA Algorithm Explained Using Simple Pencil and Paper Method

The RSA Algorithm Explained Using Simple Pencil and Paper Method

Here is what we want to do: We have a "piece of data" that we want to somehow "scramble" so nobody can learn what this data is, and we want to send this data over unsecure lines to the recipient. Upon receipt of this scrambled data, the recipient must be able to "unscramle" this data to its original shape. The important thing here is that we want to do this "scrambling/unscrambling" process without requiring usage of any secret keys that both the sender and the recipient must posses in order to scramble and descramble the data. This is why the method we are going to discuss here is called "Public Key Cryptography". There are several Public Key Cryptography algorithms in use today. The most popular is called RSA algorithm, and is named after the initials of its inventors: R for Rivest, S for Shamir, and A for Adelman. By the way, they were students when they invented this algorithm. This is their picture at the time.

So here is the summary of operations. Please continue reading below for the detailed explanation of how this is achieved. Let's say that your WEB Browser has a piece of data, say number 14 (we'll call it a Plain message and label it as P=14). and it wants to encrypt this Plain message first and then send it to the Server. Upon receipt of this encrypted message, the Server wants to decrypt it to its original value. Here is the summary of what transpires. Before any communication happens, the Server had calculated, in advance, its public (n =33 and k=7) and private (j=3) keys. Now, to initiate the transaction, the Browser sends this message to the server: Hey Server, please send me your public key. The Server obliges: Here it comes, it's n=33, k=7. After receiving the Server's public key, the Browser converts the Plain message P=14 into the Encrypted message E=20 and sends it to the Server. The Server receives this encrypted message E=20 and using its secret key j=3 (and publicly known key n=33) decrypts the E=20 message into its original Plain message P=14.

Now, let's look a bit more into the math behind all this.

Section1. Generating Public and Private Keys
First, as we mentioned above, before any transmission happens, the Server had calculated its public and secret keys.  Here is how.

1.1) pick two prime numbers, we'll pick p = 3 and q = 11
1.2) calculate n = p * q = 3 * 11 = 33
1.3) calculate z = ( p - 1 ) * ( q - 1 ) = ( 3 - 1 ) * ( 11 - 1 ) = 20
1.4) choose a prime number k, such that k is co-prime to z, i.e, z is not divisible by k. We have several choices for k: 7, 11, 13, 17, 19 (we cannot use 5, because 20 is divisible by 5). Let's pick k=7 (smaller k, "less math").
1.5) So, the numbers n = 33 and k = 7 become the Server's public key.
1.6) Now, still done in advance of any transmission, the Server has to calculate it's secret key. Here is how.
1.7) k * j = 1 ( mod z )
1.8) 7 * j = 1 ( mod 20 )
1.9) ( 7 * j ) / 20 = ? with the remainder of 1 (the "?" here means: "something, but don't wory about it"; we are only interested in the remainder). Since we selected (on purpose) to work with small numbers, we can easily conclude that 21 / 20 gives "something" with the remainder of 1. So, 7 * j = 21, and j = 3. This is our secret key. We MUST NOT give this key away.

Now, after the Server has done the above preparatory calculations in advance, we can begin our message transmission from our Browser to the Server. First, the Browser requests from the Server, the Server's public key, which the Server obliges, i.e., it sends n=33 and k=7 back to the Browser.  Now, we said that the Browser has a Plain message P=14, and it wants to encrypt it, before sending it to the Server. Here is how the encryption happens on the Browser.

Section 2. Encrypting the message

Here is the encryption math that Browser executes.

2.1) P ^ k = E ( mod n )
"^" means "to the power of"
P is the Plain message we want to encrypt
n and k are Server's public key (see Section 1)
E is our Encrypted message we want to generate

After plugging in the values, this equation is solved as follows:
2.2) 14 ^ 7 = E ( mod 33 )
This equation in English says: raise 14 to the power of 7, divide this by 33, giving the remainder of E.
2.3) 105413504 / 33 = 3194348.606 (well, I lied when I said that this is "Pencil and Paper" method only. You might want to use a calculator here).
2.4) 3194348 * 33 = 10541348
2.5) E = 105413504 - 10541348 = 20

So, our Encrypted message is E=20.  This is now the value that the Browser is going to send to the Server. When the Server receives this message, it then proceeds to Decrypt it, as follows.

Section 3. Decrypting the Message

Here is the decryption math the Server executes to recover the original Plain text message which the Browser started with.

3.1) E ^ j = P ( mod n)
E is the Encrypted message just received
j is the Server's secret key
P is the Plain message we are trying to recover
n is Server's public key (well part of; remember that Server's public key was calculated in Section 1 as consisting of two numbers: n=33 and k=7).

After plugging in the values:
3.2) 20 ^ 3 = P ( mod 33 )
3.3) 8000 / 33 = ? with the remainder of P.  So to calculate this remainder, we do:
3.4) 8000 / 33 = 242.424242...
3.5) 242 * 33 = 7986
3.6) P = 8000 - 7986 = 14, which is exactly the Plain text message that the Browser started with!

Well that's about it. While we did not discuss the theory behind the formulae involved I hope that you got at least a basic idea of how the public key cryptography using the RSA algorithm works.

Section 4. "Cracking the Code"

The essential requirement of the Public Key Cryptography is that the public and secret keys are mathematically related, but this relationship must be made very hard to determine by an outsider.  As you saw in the preceeding text, everything starts with  p and q, from which we calculated n. The public key consists of two numbers: n and k, where k is calculated from z and z is calculated from p and q. The secret key j, was calculated from k and z and,  as we just stated,  k and z are calculated from p and q. It follows then, that j is also calculated from p and q,which proves that the public and private keys are mathematically related.  So, if an outsider wanted to find the secret key j, by only knowing n, he must break down n into the two prime numbers that were used to produce it (remember that n = p * q). Now, here is the real crux of the bisquit: Decomposing a very large n into p and q is really difficult to do. It is easy with the small numbers that we have used in our demonstration, but try, for example decomposing p into p and q when p has several hundred digits. Well, if you have some free time on your hands, try this challenge. You may even earn some money. 

RSA Algorithm

The RSA algorithm is named after Ron Rivest, Adi Shamir and Len Adleman, who invented it in 1977 [RIVE78]. The basic technique was first discovered in 1973 by Clifford Cocks [COCK73] of CESG (part of the British GCHQ) but this was a secret until 1997. The patent taken out by RSA Labs has expired.
The RSA cryptosystem is the most widely-used public key cryptography algorithm in the world. It can be used to encrypt a message without the need to exchange a secret key separately.
The RSA algorithm can be used for both public key encryption and digital signatures. Its security is based on the difficulty of factoring large integers.
Party A can send an encrypted message to party B without any prior exchange of secret keys. A just uses B's public key to encrypt the message and B decrypts it using the private key, which only he knows. RSA can also be used to sign a message, so A can sign a message using their private key and B can verify it using A's public key.
We look into the mathematics behind the algorithm on our RSA Theory page.

Key Generation Algorithm

This is the original algorithm.

1. Generate two large random primes, p and q, of approximately equal size such that their product n = pq is of the required bit length, e.g. 1024 bits. [See note 1].
2. Compute n = pq and (phi) φ = (p-1)(q-1). [See note 6].
3. Choose an integer e, 1 < e < phi, such that gcd(e, phi) = 1. [See note 2].
4. Compute the secret exponent d, 1 < d < phi, such that ed ≡ 1 (mod phi). [See note 3].
5. The public key is (n, e) and the private key (d, p, q). Keep all the values d, p, q and phi secret. [We prefer sometimes to write the private key as (n, d) because you need the value of n when using d. Other times we might write the key pair as ((N, e), d).]

• n is known as the modulus.
• e is known as the public exponent or encryption exponent or just the exponent.
• d is known as the secret exponent or decryption exponent.

A practical key generation algorithm

Incorporating the advice given in the notes below, a practical algorithm to generate an RSA key pair is given below. Typical bit lengths are k = 1024, 2048, 3072, 4096,..., with increasing computational expense for larger values. You will not go far wrong if you choose e as 65537 (=0x10001) in step (1).

---

Algorithm: Generate an RSA key pair.

---

INPUT: Required modulus bit length, k.
OUTPUT: An RSA key pair ((N,e), d) where N is the modulus, the product of two primes (N=pq) not exceeding k bits in length; e is the public exponent, a number less than and coprime to (p-1)(q-1); and d is the private exponent such that ed ≡ 1 (mod (p-1)(q-1)).

1. Select a value of e from {3, 5, 17, 257, 65537}
2. repeat
3.    p ← genprime(k/2)
4. until (p mod e) ≠ 1
5. repeat
6.    q ← genprime(k - k/2)
7. until (q mod e) ≠ 1
8. N ← pq
9. L ← (p-1)(q-1)
10. d ← modinv(e, L)
11. return (N, e, d)

---

The function genprime(b) returns a prime of exactly b bits, with the bth bit set to 1. Note that the operation k/2 is integer division giving the integer quotient with no fraction.
If you've chosen e = 65537 then the chances are that the first prime returned in steps (3) and (6) will pass the tests in steps (4) and (7), so each repeat-until loop will most likely just take one iteration. The final value of N may have a bit length slightly short of the target k. This actually does not matter too much (providing the message m is always < N), but some schemes require a modulus of exact length. If this is the case, then just repeat the entire algorithm until you get one. It should not take too many goes. Alternatively, use the trick setting the two highest bits in the prime candidates described in note 1.

Encryption

Sender A does the following:-

1. Obtains the recipient B's public key (n, e).
2. Represents the plaintext message as a positive integer m, 1 < m < n [see note 4].
3. Computes the ciphertext c = m^e mod n.
4. Sends the ciphertext c to B.

Decryption

Recipient B does the following:-

1. Uses his private key (n, d) to compute m = c^d mod n.
2. Extracts the plaintext from the message representative m.

Digital signing

Sender A does the following:-

1. Creates a message digest of the information to be sent.
2. Represents this digest as an integer m between 1 and n-1. [See note 5].
3. Uses her private key (n, d) to compute the signature s = m^d mod n.
4. Sends this signature s to the recipient, B.

Signature verification

Recipient B does the following:-

1. Uses sender A's public key (n, e) to compute integer v = s^e mod n.
2. Extracts the message digest from this integer.
3. Independently computes the message digest of the information that has been signed.
4. If both message digests are identical, the signature is valid.

Notes on practical applications

1. To generate the primes p and q, generate a random number of bit length k/2 where k is the required bit length of the modulus n; set the low bit (this ensures the number is odd) and set the two highest bits (this ensures that the high bit of n is also set); check if prime (use the Rabin-Miller test); if not, increment the number by two and check again until you find a prime. This is p. Repeat for q starting with a random integer of length k-k/2. If p<q, swop p and q (this only matters if you intend using the CRT form of the private key). In the extremely unlikely event that p = q, check your random number generator. Alternatively, instead of incrementing by 2, just generate another random number each time. There are stricter rules in ANSI X9.31 to produce strong primes and other restrictions on p and q to minimise the possibility of known techniques being used against the algorithm. There is much argument about this topic. It is probably better just to use a longer key length.
   
2. In practice, common choices for e are 3, 5, 17, 257 and 65537 (2¹⁶+1). These particular values are chosen because they are primes and make the modular exponentiation operation faster, having only two bits of value 1.
   Aside: These five numbers are the first five Fermat numbers, referred to as F₀ to F₄, where . Just be careful, these first five Fermat numbers are prime ("Fermat primes"), but the numbers F₅ and above are not prime. For example, F₅ = 4294967297 = 641 × 6700417.
   The usual choice for e is F4 = 65537 = 0x10001. Also, having chosen e, it is simpler to test whether gcd(e, p-1)=1 and gcd(e, q-1)=1 while generating and testing the primes in step 1. Values of p or q that fail this test can be rejected there and then.
   Even better: if e is an odd prime then you can do the less-expensive test (p mod e) ≠ 1 instead of gcd(p-1,e) = 1.

   Why is that? If e is prime then gcd(p-1, e) > 1 if and only if p-1 is a multiple of e. That is, if p - 1 ≡ 0 (mod e) or p ≡ 1 (mod e). Hence gcd(p-1, e) = 1 ⇔ p mod e ≠ 1.
3. To compute the value for d, use the Extended Euclidean Algorithm to calculate d = e^-1 mod phi, also written d = (1/e) mod phi. This is known as modular inversion. Note that this is not integer division. The modular inverse d is defined as the integer value such that ed = 1 mod phi. It only exists if e and phi have no common factors.
4. When representing the plaintext octets as the representative integer m, it is important to add random padding characters to make the size of the integer m large and less susceptible to certain types of attack. If m = 0 or 1 or n-1 there is no security as the ciphertext has the same value. For more details on how to represent the plaintext octets as a suitable representative integer m, see PKCS#1 Schemes below or the reference itself [PKCS1]. It is important to make sure that m < n otherwise the algorithm will fail. This is usually done by making sure the first octet of m is equal to 0x00.
5. Decryption and signing are identical as far as the mathematics is concerned as both use the private key. Similarly, encryption and verification both use the same mathematical operation with the public key. That is, mathematically, for m < n,
   m = (m^e mod n)^d mod n = (m^d mod n)^e mod n
   However, note these important differences in implementation:-
   
   • The signature is derived from a message digest of the original information. The recipient will need to follow exactly the same process to derive the message digest, using an identical set of data.
   • The recommended methods for deriving the representative integers are different for encryption and signing (encryption involves random padding, but signing uses the same padding each time).
6. The original definition of RSA uses the Euler totient function φ(n) = (p-1)(q-1). More recent standards use the Charmichael function λ(n) = lcm(p-1, q-1) instead. λ(n) is smaller than φ(n) and divides it. The value of d' computed by d' = e^-1 mod λ(n) is usually different from that derived by d = e^-1 mod φ(n), but the end result is the same. Both d and d' will decrypt a message m^e mod n and both will give the same signature value s = m^d mod n = m^d' mod n. To compute λ(n), use the relation

       λ(n) = (p-1)(q-1) / gcd(p-1, q-1).
   

7. You might ask if there is a way to find the factors of n given just d and e. This is possible. 

Summary of RSA

• n = pq, where p and q are distinct primes.
• phi, φ = (p-1)(q-1)
• e < n such that gcd(e, phi)=1
• d = e^-1 mod phi.
• c = m^e mod n, 1<m<n.
• m = c^d mod n.

For more on the theory and mathematics behind the algorithm, see the RSA Theory page.

Key length

When we talk about the key length of an RSA key, we are referring to the length of the modulus, n, in bits. The minimum recommended key length for a secure RSA transmission is currently 1024 bits. A key length of 512 bits is now no longer considered secure, although cracking it is still not a trivial task for the likes of you and me. The longer your information is needed to be kept secure, the longer the key you should use. Keep up to date with the latest recommendations in the security journals.
There is one small area of confusion in defining the key length. One convention is that the key length is the position of the most significant bit in n that has value '1', where the least significant bit is at position 1. Equivalently, key length = ceiling(log₂(n+1)). The other convention, sometimes used, is that the key length is the number of bytes needed to store n multiplied by eight, i.e. ceiling(log₂₅₆(n+1))*8.
The key used in the RSA Example paper [KALI93] is an example. In hex form the modulus is

0A 66 79 1D C6 98 81 68 DE 7A B7 74 19 BB 7F B0
C0 01 C6 27 10 27 00 75 14 29 42 E1 9A 8D 8C 51
D0 53 B3 E3 78 2A 1D E5 DC 5A F4 EB E9 94 68 17
01 14 A1 DF E6 7C DC 9A 9A F5 5D 65 56 20 BB AB

The most significant byte 0x0A in binary is 00001010'B. The most significant bit is at position 508, so its key length is 508 bits. On the other hand, this value needs 64 bytes to store it, so the key length could also be referred to by some as 64 x 8 = 512 bits. We prefer the former method. You can get into difficulties with the X9.31 method for signatures if you use the latter convention.

Minimum key lengths

The following table is taken from NIST's Recommendation for Key Management [NIST-80057]. It shows the recommended comparable key sizes for symmetrical block ciphers (AES and Triple DES) and the RSA algorithm. That is, the key length you would need to use to have comparable security.

Symmetric key algorithm	Comparable RSA key length	Comparable hash function	Bits of security
2TDEA*	1024	SHA-1	80
3TDEA	2048	SHA-224	112
AES-128	3072	SHA-256	128
AES-192	7680	SHA-384	192
AES-256	15360	SHA-512	256

* 2TDEA is 2-key triple DES - see What's two-key triple DES encryption.

Note just how huge (and impractical) an RSA key needs to be for comparable security with AES-192 or AES-256 (although these two algorithms have had some weaknesses exposed recently; AES-128 is unaffected).
The above table is a few years old now and may be out of date. Existing cryptographic algorithms only get weaker as attacks get better.

Computational Efficiency and the Chinese Remainder Theorem (CRT)

Key generation is only carried out occasionally and so computational efficiency is less of an issue.
The calculation a = b^e mod n is known as modular exponentiation and one efficient method to carry this out on a computer is the binary left-to-right method. To solve y = x^e mod n let e be represented in base 2 as
e = e_(k-1)e_(k-2)...e₍₁₎e₍₀₎
where e(k-1) is the most significant non-zero bit and bit e(0) the least.

set y = x
for bit j = k - 2 downto 0 
begin
  y = y * y mod n   /* square */
  if e(j) == 1 then
    y = y * x mod n  /* multiply */
end
return y

The time to carry out modular exponentation increases with the number of bits set to one in the exponent e. For encryption, an appropriate choice of e can reduce the computational effort required to carry out the computation of c = m^e mod n. Popular choices like 3, 17 and 65537 are all primes with only two bits set: 3 = 0011'B, 17 = 0x11, 65537 = 0x10001.
The bits in the decryption exponent d, however, will not be so convenient and so decryption using the standard method of modular exponentiation will take longer than encryption. Don't make the mistake of trying to contrive a small value for d; it is not secure.
An alternative method of representing the private key uses the The Chinese Remainder Theorem (CRT).

The private key is represented as a quintuple (p, q, dP, dQ, and qInv), where p and q are prime factors of n, dP and dQ are known as the CRT exponents, and qInv is the CRT coefficient. The CRT method of decryption is about four times faster overall than calculating m = c^d mod n. The extra values for the private key are:-

dP = (1/e) mod (p-1)
dQ = (1/e) mod (q-1)
qInv = (1/q) mod p  where p > q

where the (1/e) notation means the modular inverse (see note 3 above). These values are pre-computed and saved along with p and q as the private key. To compute the message m given c do the following:-

m1 = c^dP mod p
m2 = c^dQ mod q
h = qInv(m1 - m2) mod p
m = m2 + hq

Even though there are more steps in this procedure, the modular exponentation to be carried out uses much shorter exponents and so it is less expensive overall.
[2008-09-02] Chris Becke has pointed out that most large integer packages will fail when computing h if m1 < m2. This can be easily fixed by computing

h = qInv(m1 + p - m2) mod p

or, alternatively, as we do it in our BigDigits implementation of RSA,

 if (bdCompare(m1, m2) < 0)
    bdAdd(m1, m1, p);
 bdSubtract(m1, m1, m2);
 /* Let h = qInv ( m_1 - m_2 ) mod p. */
 bdModMult(h, qInv, m1, p);

A very simple example of RSA encryption

This is an extremely simple example using numbers you can work out on a pocket calculator (those of you over the age of 35 45 can probably even do it by hand).

1. Select primes p=11, q=3.
2. n = pq = 11.3 = 33
   phi = (p-1)(q-1) = 10.2 = 20
3. Choose e=3
   Check gcd(e, p-1) = gcd(3, 10) = 1 (i.e. 3 and 10 have no common factors except 1),
   and check gcd(e, q-1) = gcd(3, 2) = 1
   therefore gcd(e, phi) = gcd(e, (p-1)(q-1)) = gcd(3, 20) = 1
4. Compute d such that ed ≡ 1 (mod phi)
   i.e. compute d = e^-1 mod phi = 3^-1 mod 20
   i.e. find a value for d such that phi divides (ed-1)
   i.e. find d such that 20 divides 3d-1.
   Simple testing (d = 1, 2, ...) gives d = 7
   Check: ed-1 = 3.7 - 1 = 20, which is divisible by phi.
5. Public key = (n, e) = (33, 3)
   Private key = (n, d) = (33, 7).

This is actually the smallest possible value for the modulus n for which the RSA algorithm works. Now say we want to encrypt the message m = 7,
c = m^e mod n = 7³ mod 33 = 343 mod 33 = 13.
Hence the ciphertext c = 13.
To check decryption we compute
m' = c^d mod n = 13⁷ mod 33 = 7.
Note that we don't have to calculate the full value of 13 to the power 7 here. We can make use of the fact that
a = bc mod n = (b mod n).(c mod n) mod n
so we can break down a potentially large number into its components and combine the results of easier, smaller calculations to calculate the final value.
One way of calculating m' is as follows:-
Note that any number can be expressed as a sum of powers of 2. So first compute values of 13², 13⁴, 13⁸, ... by repeatedly squaring successive values modulo 33.
13² = 169 ≡ 4, 13⁴ = 4.4 = 16, 13⁸ = 16.16 = 256 ≡ 25.
Then, since 7 = 4 + 2 + 1, we have m' = 13⁷ = 13^(4+2+1) = 13⁴.13².13¹
≡ 16 x 4 x 13 = 832 ≡ 7 mod 33

Now if we calculate the ciphertext c for all the possible values of m (0 to 32), we get

m  0  1  2  3  4  5  6  7  8  9 10 11 12 13 14 15 16
c  0  1  8 27 31 26 18 13 17  3 10 11 12 19  5  9  4

m 17 18 19 20 21 22 23 24 25 26 27 28 29 30 31 32
c 29 24 28 14 21 22 23 30 16 20 15  7  2  6 25 32

Note that all 33 values of m (0 to 32) map to a unique code c in the same range in a sort of random manner. In this case we have nine values of m that map to the same value of c - these are known as unconcealed messages. m = 0, 1 and n-1 will always do this for any n, no matter how large. But in practice, these shouldn't be a problem when we use large values for n in the order of several hundred bits.
If we wanted to use this system to keep secrets, we could let A=2, B=3, ..., Z=27. (We specifically avoid 0 and 1 here for the reason given above). Thus the plaintext message "HELLOWORLD" would be represented by the set of integers m₁, m₂, ...

(9,6,13,13,16,24,16,19,13,5)

Using our table above, we obtain ciphertext integers c₁, c₂, ...

(3,18,19,19,4,30,4,28,19,26)

Note that this example is no more secure than using a simple Caesar substitution cipher, but it serves to illustrate a simple example of the mechanics of RSA encryption. Remember that calculating m^e mod n is easy, but calculating the inverse c^-e mod n is very difficult, well, for large n's anyway. However, if we can factor n into its prime factors p and q, the solution becomes easy again, even for large n's. Obviously, if we can get hold of the secret exponent d, the solution is easy, too.

A slightly less simple example of the RSA algorithm

[Updated 25 November 2012] This time, to make life slightly less easy for those who can crack simple Caesar substitution codes, we will group the characters into blocks of three and compute a message representative integer for each block. Please note that this method is not secure in any way. It just shows another example of the mechanism of RSA with small numbers.
For this example, to keep things simple, we'll limit our characters to the letters A to Z and the space character.

ATTACK AT SEVEN = ATT ACK _AT _SE VEN

In the same way that any decimal number can be represented uniquely as the sum of powers of ten, e.g.
135 = 1 x 10² + 3 x 10¹ + 5,
we can represent our blocks of three characters as the sum of powers of 27 using SPACE=0, A=1, B=2, C=3, .. E=5, .. K=11, .. N=14, .. S=19, T=20, .. V=22, ..., Z=26.

ATT ⇒ 1 x 27² + 20 x 27¹ + 20 = 1289
ACK ⇒ 1 x 27² + 3 x 27¹ + 11 = 821
_AT ⇒ 0 x 27² + 1 x 27¹ + 20 = 47
_SE ⇒ 0 x 27² + 19 x 27¹ + 5 = 518
VEN ⇒ 22 x 27² + 5 x 27¹ + 14 = 16187

Using this system of integer representation, the maximum value of a block (ZZZ) is 27³-1 = 19682, so we require a modulus n greater than this value.

1. We choose e = 3
2. We select primes p=173 and q=149 and check
   • gcd(e, p-1) = gcd(3, 172) = 1 ⇒ OK
   • gcd(e, q-1) = gcd(3, 148) = 1 ⇒ OK.
3. Thus we have n = pq = 173 × 149 = 25777, and
   phi = (p-1)(q-1) = 172 × 148 = 25456.
4. We compute d = e^-1 mod phi = 3^-1 mod 25456 = 16971.
   • Note that ed = 3 × 16971 = 50913 = 2 × 25456 + 1
   • That is, ed ≡ 1 mod 25456 ≡ 1 mod phi
5. Hence our public key is (n, e) = (25777, 3) and our private key is (n, d) = (25777, 16971). We keep the values of p, q, d and phi secret.

To encrypt the first integer that represents "ATT", we have
c = m^e mod n = 1289³ mod 25777 = 18524.

Overall, our plaintext ATTACK AT SEVEN is represented by the sequence of five integers m₁, m₂, m₃, m₄, m₅:

m_i = (1289, 821, 47, 518, 16187)

We compute corresponding ciphertext integers c_i = m_i^e mod n, (which is still possible by using a calculator, honest):

c₁ = 1289³ mod 25777 = 18524
c₂ = 821³ mod 25777 = 7025
c₃ = 47³ mod 25777 = 715
c₄ = 518³ mod 25777 = 2248
c₅ = 16187³ mod 25777 = 24465

We can send this sequence of integers, c_i, to the person who has the private key.

c_i = (18524, 7025, 715, 2248, 24465)

We can compute the inverse of these ciphertext integers using m = c^d mod n to verify that the RSA algorithm still holds. However, this is now outside the realm of hand calculations.
To help you carry out these modular arithmetic calculations, download our free modular arithmetic command line programs.
For example, to compute 1852416971 mod 25777, use the bd_modexp command:

bd_modexp 18524 16971 25777
18524^16971 mod 25777 = 1289

You should get the results:

m₁ = 18524¹⁶⁹⁷¹ mod 25777 = 1289
m₂ = 7025¹⁶⁹⁷¹ mod 25777 = 821
m₃ = 715¹⁶⁹⁷¹ mod 25777 = 47
m₄ = 2248¹⁶⁹⁷¹ mod 25777 = 518
m₅ = 24465¹⁶⁹⁷¹ mod 25777 = 16187

To convert these integers back to the block of three letters, do the following. For example, given m = 16187,

16187 ÷ 27² = 16187 ÷ 729 = 22 rem 149, 22 → 'V'
149 ÷ 27¹ = 149 ÷ 27 = 5 rem 14, 5 → 'E'
14 ÷ 27⁰ = 14 ÷ 1 = 14 rem 0, 14 → 'N'

Hence the integer m = 16187 represents the string "VEN".

Similarly, m = 47 is encoded as follows: 47 ÷ 272 = 0 rem 47, 0 → SPACE; 47 ÷ 271 = 1 rem 20, 1 → 'A'; 20 ÷ 270 = 20 rem 0, 20 → 'T' giving the string "_AT".
Question: Why can't we use this method of encoding integers into blocks of three letters to encode the ciphertext?

A caution about this example

Note that this example is a very insecure method of encryption and should not be used in practice. We can easily factorize the modulus and hence break the cipher.

Factorising a small RSA modulus

Starting with the knowledge that the modulus 25777 is the product of exactly two distinct prime numbers, and that one of these must be less than its integer square root (why?), a little testing of suitable candidates from a table of prime numbers will get you the answer pretty quickly.

Given n = 25777, compute √25777 = 160.55, and then work downwards through the prime numbers < 160, i.e. (157, 151, 149, 139, ...), and try to divide into n in turn:
  157: 25777 / 157 = 164 remainder 29, so not a factor;
  151: 25777 / 151 = 170 remainder 107, so not a factor;
  149: 25777 / 149 = 173 exactly, so we have it.

You could also write a simple computer program to factor n that just divides it by every odd number starting from 3 until it either finds an exact factor or stops when it reaches a number greater than the square root of n.

A real example

In practice, we use a modulus of size in the order of 1024 bits. That is a number over 300 decimal digits long. One example is

n = 
11929413484016950905552721133125564964460656966152763801206748195494305685115033
38063159570377156202973050001186287708466899691128922122454571180605749959895170
80042105263427376322274266393116193517839570773505632231596681121927337473973220
312512599061231322250945506260066557538238517575390621262940383913963

This is composed of the two primes

p = 
10933766183632575817611517034730668287155799984632223454138745671121273456287670
008290843302875521274970245314593222946129064538358581018615539828479146469

q = 
10910616967349110231723734078614922645337060882141748968209834225138976011179993
394299810159736904468554021708289824396553412180514827996444845438176099727

With a number this large, we can encode all the information we need in one big integer. We put our message into an octet string and then convert to a large integer.
Also, rather than trying to represent the plaintext as an integer directly, we generate a random session key and use that to encrypt the plaintext with a conventional, much faster symmetrical algorithm like Triple DES or AES-128. We then use the much slower public key encryption algorithm to encrypt just the session key.
The sender A then transmits a message to the recipient B in a format something like this:-

Session key encrypted with RSA = xxxx
Plaintext encrypted with session key = xxxxxxxxxxxxxxxxx

The recipient B would extract the encrypted session key and use his private key (n,d) to decrypt it. He would then use this session key with a conventional symmetrical decryption algorithm to decrypt the actual message. Typically the transmission would include in plaintext details of the encryption algorithms used, padding and encoding methods, initialisation vectors and other details required by the recipient. The only secret required to be kept, as always, should be the private key.
If Mallory intercepts the transmission, he can either try and crack the conventionally-encrypted plaintext directly, or he can try and decrypt the encryped session key and then use that in turn. Obviously, this system is as strong as its weakest link.
When signing, it is usual to use RSA to sign the message digest of the message rather than the message itself. A one-way hash function like SHA-1 or SHA-256 is used. The sender A then sends the signed message to B in a format like this

Hash algorithm = hh
Message content = xxxxxxxxx...xxx
Signature = digest signed with RSA = xxxx

The recipient will decrypt the signature to extract the signed message digest, m; independently compute the message digest, m', of the actual message content; and check that m and m' are equal. Putting the message digest algorithm at the beginning of the message enables the recipient to compute the message digest on the fly while reading the message.

Difference between 8-bit and 16-bit Microprocessor

8-bit v 16-bit Microprocessor
Before illustrating you the difference between 8-bit and 16-bit microprocessor, Let me illustrate you the what actually this “8-bit” or “16-bit mean”. An 8-bit CPU and ALU architectures are those that are based on registers, address buses, or data buses of that size. 8-bit is also a term given to a generation of microcomputers in which 8-bit microprocessors were the norm and for 16-bit it is the vice-versa.
Lets know some interesting concept which leads us to know the difference between 8-bit ad 16-bit Microprocessor.

What is the difference between 8-bit and 16-bit Microprocessor ?

Difference between 8-bit and 16-bit Microprocessor

8-bit v 16-bit Microprocessor
Before illustrating you the difference between 8-bit and 16-bit microprocessor, Let me illustrate you the what actually this “8-bit” or “16-bit mean”. An 8-bit CPU and ALU architectures are those that are based on registers, address buses, or data buses of that size. 8-bit is also a term given to a generation of microcomputers in which 8-bit microprocessors were the norm and for 16-bit it is the vice-versa.
Lets know some interesting concept which leads us to know the difference between 8-bit ad 16-bit Microprocessor.

What is the difference between 8-bit and 16-bit Microprocessor ?

In June of 1978, Intel introduced the revolutionary new processor called the 8086. It was one of the first 16-bit processor chips on the market, at that time most of the all other processors had 8-bit design architecture.

Difference between 8-bit and 16-bit Microprocessor

8-bit v 16-bit Microprocessor
Before illustrating you the difference between 8-bit and 16-bit microprocessor, Let me illustrate you the what actually this “8-bit” or “16-bit mean”. An 8-bit CPU and ALU architectures are those that are based on registers, address buses, or data buses of that size. 8-bit is also a term given to a generation of microcomputers in which 8-bit microprocessors were the norm and for 16-bit it is the vice-versa.
Lets know some interesting concept which leads us to know the difference between 8-bit ad 16-bit Microprocessor.

What is the difference between 8-bit and 16-bit Microprocessor ?

In June of 1978, Intel introduced the revolutionary new processor called the 8086. It was one of the first 16-bit processor chips on the market, at that time most of the all other processors had 8-bit design architecture.

Intel 8086 Characteristics

3 um process

29k transistors

5-10 MHz

16-bit word size

16-bit external-internal bus size

40-pin DIP package

The 8086 had 16-bit internal registers and people started running new softwares using 16-bit instructions. It has an 16- bit external data bus, which means it could transfer data to memory 16 bits at a time.
And the address bus was 20 bits wide, which means that the 8086 can address a full 1MB (2^20) of memory. This made a stark contrast to most other chips of that time that which had 8-bit internal registers, an 8-bit external data bus, and a 16-bit address bus allowing a maximum of only 64KB of RAM (2^16).
Unfortunately, most of the personal computer world at that time was using 8-bit processors, which ran 8-bit Control Instructions for operating systems and software. And the board and circuit designs at that time were mostly 8-bit as well. Building a full 16-bit microprocessor and memory system would be very costly.

The cost was very high as the 8086 needed a 16-bit data bus rather than a less expensive 8-bit bus. As all the systems available at that time were 8-bit, and sales were also very low as of the 8086 indicated and this made Intel to think that people weren’t willing to pay for the extra performance of the full 16-bit design.
As a result, Intel introduced a new kind of crippled version of the 8086, called the 8088. The 8088 essentially deleted 8 of the 16 bits on the data bus, making the 8088 an 8-bit chip as far as data input and output were concerned. Anyways as it retained the full 16-bit internal registers and the 20-bit address bus, the 8088 ran 16-bit software and was capable of addressing a full 1MB of RAM.
So the main difference is speed that is the frequency at which the instructions per cycle are executed
The following two are the microprocessors which are introduced by Intel which led to the evolution of 16-bit microprocessor
First Intel processor aftr 4004 series

Intel 8008 Characteristics

10 um process

3500 transistors

500 – 800 kHz

Do Memory Retention exercises

8-bit word size

18-pin DIP package

Intel 8080 Characteristics

6 um process

4500 transistors

2 MHz

8-bit word size

40-pin DIP package

 

 

What is the difference between a LAN, a MAN, and a WAN?

Home >> Computers >> Difference Between LAN, MAN and WAN

Difference Between LAN, MAN and WAN

LAN vs MAN vs WAN
The terms LAN, MAN, WAN are terms widely used in Technology (Internet world). Here, we will list out the differences between them. Read point to point differences between LAN and MAN and WAN.

LAN

Read more: http://www.differencebetween.co.in/computers/difference-between-lan-man-and-wan/#ixzz3k6VJtbR8

 

1. LAN (Local Area Network) is a group of computers and other network devices which are connected together.
2. All the devices that are part of LAN are within a building or multiple building.
3. LAN network has very high speed mainly due to proximity of computer and network devices.
4. LAN connection speeds can be 10Mbps or 100Mbps or 1000Mpbs also.
5. LAN uses Guided Media

Read more: http://www.differencebetween.co.in/computers/difference-between-lan-man-and-wan/#ixzz3k6VPpTHx

 

Home >> Computers >> Difference Between LAN, MAN and WAN

Difference Between LAN, MAN and WAN

LAN vs MAN vs WAN
The terms LAN, MAN, WAN are terms widely used in Technology (Internet world). Here, we will list out the differences between them. Read point to point differences between LAN and MAN and WAN.

LAN

1. LAN (Local Area Network) is a group of computers and other network devices which are connected together.
2. All the devices that are part of LAN are within a building or multiple building.
3. LAN network has very high speed mainly due to proximity of computer and network devices.
4. LAN connection speeds can be 10Mbps or 100Mbps or 1000Mpbs also.
5. LAN uses Guided Media

MAN

1. MAN ((Metropolitan Area Network) is a larger network of computers and other network devices which are connected together usually spans serveral buildings or large geographical area.
2. All the devices that are part of MAN are span across buildings or small town.
3. MAN network has lower speed compared to LAN.
4. MAN connection speeds can be 10Mbps or 100Mbps.
5. MAN uses Guided Media or Unguided media.

WAN

1. WAN (Wide Area Network) is a group of computers and other network devices which are connected together which is not restricted to a geographical location. Internet is WAN
2. All the devices that are part of WAN have no geographical boundaries.
3. WAN speed varies based on geographical location of the servers. WAN connects serveral LANs
4. WAN connection speeds can be 10Mbps or 100Mbps.
5. WAN mainly uses Guided Media or Unguided media. Its long distance communications, which may or may not be provided by public packet network.

Read more: http://www.differencebetween.co.in/computers/difference-between-lan-man-and-wan/#ixzz3k6VViiw3

 

What is the difference between a LAN, a MAN, and a WAN?

A LAN (local area network) is a group of computers and network devices connected together, usually within the same building. By definition, the connections must be high speed and relatively inexpensive (e.g., token ring or Ethernet). Most Indiana University Bloomington departments are on LANs.
A LAN connection is a high-speed connection to a LAN. On the IUB campus, most connections are either Ethernet (10 Mbps) or Fast Ethernet (100 Mbps), and a few locations have Gigabit Ethernet (1000 Mbps) connections.
A MAN (metropolitan area network) is a larger network that usually spans several buildings in the same city or town. The IUB network is an example of a MAN.
A WAN (wide area network), in comparison to a MAN, is not restricted to a geographical location, although it might be confined within the bounds of a state or country. A WAN connects several LANs, and may be limited to an enterprise (a corporation or an organization) or accessible to the public. The technology is high speed and relatively expensive. The Internet is an example of a worldwide public WAN.

 

 

 

 

JavaScript Operators

JavaScript Operators
JavaScript operators are symbols that are used to perform operations on operands. For example:

    var sum=10+20; 

Here, + is the arithmetic operator and = is the assignment operator.

There are following types of operators in JavaScript.

    Arithmetic Operators
    Comparison (Relational) Operators
    Bitwise Operators
    Logical Operators
    Assignment Operators
    Special Operators

JavaScript Arithmetic Operators

Arithmetic operators are used to perform arithmetic operations on the operands. The following operators are known as JavaScript arithmetic operators.
Operator    Description    Example
+    Addition    10+20 = 30
-    Subtraction    20-10 = 10
*    Multiplication    10*20 = 200
/    Division    20/10 = 2
%    Modulus (Remainder)    20%10 = 0
++    Increment    var a=10; a++; Now a = 11
--    Decrement    var a=10; a--; Now a = 9
JavaScript Comparison Operators

The JavaScript comparison operator compares the two operands. The comparison operators are as follows:
Operator    Description    Example
==    Is equal to    10==20 = false
===    Identical (equal and of same type)    10==20 = false
!=    Not equal to    10!=20 = true
!==    Not Identical    20!==20 = false
>    Greater than    20>10 = true
>=    Greater than or equal to    20>=10 = true
<    Less than    20<10 = false
<=    Less than or equal to    20<=10 = false
JavaScript Bitwise Operators

The bitwise operators perform bitwise operations on operands. The bitwise operators are as follows:
Operator    Description    Example
&    Bitwise AND    (10==20 & 20==33) = false
|    Bitwise OR    (10==20 | 20==33) = false
^    Bitwise XOR    (10==20 ^ 20==33) = false
~    Bitwise NOT    (~10) = -10
<<    Bitwise Left Shift    (10<<2) = 40
>>    Bitwise Right Shift    (10>>2) = 2
>>>    Bitwise Right Shift with Zero    (10>>>2) = 2
JavaScript Logical Operators

The following operators are known as JavaScript logical operators.
Operator    Description    Example
&&    Logical AND    (10==20 && 20==33) = false
||    Logical OR    (10==20 || 20==33) = false
!    Logical Not    !(10==20) = true
JavaScript Assignment Operators

The following operators are known as JavaScript assignment operators.
Operator    Description    Example
=    Assign    10+10 = 20
+=    Add and assign    var a=10; a+=20; Now a = 30
-=    Subtract and assign    var a=20; a+=10; Now a = 10
*=    Multiply and assign    var a=10; a*=20; Now a = 200
/=    Divide and assign    var a=10; a/=2; Now a = 5
%=    Modulus and assign    var a=10; a%=2; Now a = 0
JavaScript Special Operators

The following operators are known as JavaScript special operators.
Operator    Description
(?:)    Conditional Operator returns value based on the condition. It is like if-else.
,    Comma Operator allows multiple expressions to be evaluated as single statement.
delete    Delete Operator deletes a property from the object.
in    In Operator checks if object has the given property
instanceof    checks if the object is an instance of given type
new    creates an instance (object)
typeof    checks the type of object.
void    it discards the expression's return value.
yield    checks what is returned in a generator by the generator's iterator.

Javascript Data Types

Javascript Data Types

JavaScript provides different data types to hold different types of values. There are two types of data types in JavaScript.

    Primitive data type
    Non-primitive (reference) data type

JavaScript is a dynamic type language, means you don't need to specify type of the variable because it is dynamically used by JavaScript engine. You need to use var here to specify the data type. It can hold any type of values such as numbers, strings etc. For example:

    var a=40;//holding number 
    var b="Rahul";//holding string 

JavaScript primitive data types

There are five types of primitive data types in JavaScript. They are as follows:
Data Type: Description
String     : represents sequence of characters e.g. "hello"
Number     : represents numeric values e.g. 100
Boolean     : represents boolean value either false or true
Undefined: represents undefined value
Null     : represents null i.e. no value at all

JavaScript non-primitive data types

The non-primitive data types are as follows:
Data Type: Description
Object     : represents instance through which we can access members
Array     : represents group of similar values
RegExp     : represents regular expression

Javascript Variables

JavaScript Variable

    JavaScript variable
    JavaScript Local variable
    JavaScript Global variable

A JavaScript variable is simply a name of storage location. There are two types of variables in JavaScript : local variable and global variable.

There are some rules while declaring a JavaScript variable (also known as identifiers).

    Name must start with a letter (a to z or A to Z), underscore( _ ), or dollar( $ ) sign.
    After first letter we can use digits (0 to 9), for example value1.
    JavaScript variables are case sensitive, for example x and X are different variables.

Correct JavaScript variables

    var x = 10; 
    var _value="sonoo"; 

Incorrect JavaScript variables

    var  123=30; 
    var *aa=320; 

Example of JavaScript variable

Let’s see a simple example of JavaScript variable.

    <script> 
    var x = 10; 
    var y = 20; 
    var z=x+y; 
    document.write(z); 
    </script> 

Output of the above example
30

JavaScript local variable

A JavaScript local variable is declared inside block or function. It is accessible within the function or block only. For example:

    <script> 
    function abc(){ 
    var x=10;//local variable 
    } 
    </script> 

Or,

    <script> 
    If(10<13){ 
    var y=20;//JavaScript local variable 
    } 
    </script> 

JavaScript global variable

A JavaScript global variable is accessible from any function. A variable i.e. declared outside the function or declared with window object is known as global variable. For example:

    <script> 
    var data=200;//gloabal variable 
    function a(){ 
    document.writeln(data); 
    } 
    function b(){ 
    document.writeln(data); 
    } 
    a();//calling JavaScript function 
    b(); 
    </script> 

JavaScript Global Variable

A JavaScript global variable is declared outside the function or declared with window object. It can be accessed from any function.

Let’s see the simple example of global variable in JavaScript.

    <script> 
    var value=50;//global variable 
    function a(){ 
    alert(value); 
    } 
    function b(){ 
    alert(value); 
    } 
    </script> 

Declaring JavaScript global variable within function

To declare JavaScript global variables inside function, you need to use window object. For example:

    window.value=90; 

Now it can be declared inside any function and can be accessed from any function. For example:

    function m(){ 
    window.value=100;//declaring global variable by window object 
    } 
    function n(){ 
    alert(window.value);//accessing global variable from other function 
    } 

Internals of global variable in JavaScript

When you declare a variable outside the function, it is added in the window object internally. You can access it through window object also. For example:

    var value=50; 
    function a(){ 
    alert(window.value);//accessing global variable  
    } 

Javascript Comments

JavaScript Comment

    JavaScript comments
    Advantage of javaScript comments
    Single-line and Multi-line comments

The JavaScript comments are meaningful way to deliver message. It is used to add information about the code, warnings or suggestions so that end user can easily interpret the code.

The JavaScript comment is ignored by the JavaScript engine i.e. embedded in the browser.
Advantages of JavaScript comments

There are mainly two advantages of JavaScript comments.

    To make code easy to understand It can be used to elaborate the code so that end user can easily understand the code.
    To avoid the unnecessary code It can also be used to avoid the code being executed. Sometimes, we add the code to perform some action. But after sometime, there may be need to disable the code. In such case, it is better to use comments.

Types of JavaScript Comments

There are two types of comments in JavaScript.

    Single-line Comment
    Multi-line Comment

JavaScript Single line Comment

It is represented by double forward slashes (//). It can be used before and after the statement.

Let’s see the example of single-line comment i.e. added before the statement.

    <script> 
    // It is single line comment 
    document.write("hello javascript"); 
    </script> 

Let’s see the example of single-line comment i.e. added after the statement.

    <script> 
    var a=10; 
    var b=20; 
    var c=a+b;//It adds values of a and b variable 
    document.write(c);//prints sum of 10 and 20 
    </script> 

JavaScript Multi line Comment

It can be used to add single as well as multi line comments. So, it is more convenient.

It is represented by forward slash with asterisk then asterisk with forward slash. For example:

    /* your code here  */ 

It can be used before, after and middle of the statement.

    <script> 
    /* It is multi line comment. 
    It will not be displayed */ 
    document.write("example of javascript multiline comment"); 
    </script>

JavaScript Tutorial

JavaScript Tutorial

javascript

JavaScript Tutorial for beginners and professionals is a solution of client side dynamic pages.

JavaScript is an object-based scripting language that is lightweight and cross-platform.

JavaScript is not compiled but translated. The JavaScript Translator (embedded in browser) is responsible to translate the JavaScript code.
Where JavaScript is used

JavaScript is used to create interactive websites. It is mainly used for:

    Client-side validation
    Dynamic drop-down menus
    Displaying data and time
    Displaying popup windows and dialog boxes (like alert dialog box, confirm dialog box and prompt dialog box)
    Displaying clocks etc.

JavaScript Example

    <h2>Welcome to JavaScript</h2> 
    <script> 
    document.write("Hello JavaScript by JavaScript"); 
    </script> 

JavaScript Example

    JavaScript Example
    Within body tag
    Within head tag

Javascript example is easy to code. JavaScript provides 3 places to put the JavaScript code: within body tag, within head tag and external JavaScript file.

Let’s create the first JavaScript example.

    <script type="text/javascript"> 
    document.write("JavaScript is a simple language for javatpoint learners"); 
    </script> 
The script tag specifies that we are using JavaScript.

The text/javascript is the content type that provides information to the browser about the data.

The document.write() function is used to display dynamic content through JavaScript. We will learn about document object in detail later.
3 Places to put JavaScript code

    Between the body tag of html
    Between the head tag of html/li>
    In .js file (external javaScript)

1) JavaScript Example : code between the body tag

In the above example, we have displayed the dynamic content using JavaScript. Let’s see the simple example of JavaScript that displays alert dialog box.

    <script type="text/javascript"> 
     alert("Hello Javatpoint"); 
    </script> 


2) JavaScript Example : code between the head tag

Let’s see the same example of displaying alert dialog box of JavaScript that is contained inside the head tag.

In this example, we are creating a function msg(). To create function in JavaScript, you need to write function with function_name as given below.

To call function, you need to work on event. Here we are using onclick event to call msg() function.

    <html> 
    <head> 
    <script type="text/javascript"> 
    function msg(){ 
     alert("Hello Javatpoint"); 
    } 
    </script> 
    </head> 
    <body> 
    <p>Welcome to JavaScript</p> 
    <form> 
    <input type="button" value="click" onclick="msg()"/> 
    </form> 
    </body> 
    </html> 

External JavaScript file

We can create external JavaScript file and embed it in many html page.

It provides code re usability because single JavaScript file can be used in several html pages.

An external JavaScript file must be saved by .js extension. It is recommended to embed all JavaScript files into a single file. It increases the speed of the webpage.

Let’s create an external JavaScript file that prints Hello Javatpoint in a alert dialog box.

message.js

    function msg(){ 
     alert("Hello Javatpoint"); 
    } 

Let’s include the JavaScript file into html page. It calls the JavaScript function on button click.

index.html

    <html> 
    <head> 
    <script type="text/javascript" src="message.js"></script> 
    </head> 
    <body> 
    <p>Welcome to JavaScript</p> 
    <form> 
    <input type="button" value="click" onclick="msg()"/> 
    </form> 
    </body> 
    </html>