Table of contents
1.
Introduction
2.
Shank’s Algorithm
2.1.
The Shank’s Algorithm Function
2.2.
Proof
2.3.
Example
3.
Frequently Asked Questions
3.1.
Differentiate Plain Text and Cipher Text.
3.2.
Why do we use Session Key?
3.3.
Describe the Blind Signature Scheme.
3.4.
Mention the importance of Encryption.
4.
Conclusion
Last Updated: Mar 27, 2024
Medium

Algorithms: It’s Shank’s not Sharks

Author Rupal Saluja
0 upvote
Career growth poll
Do you think IIT Guwahati certified course can help you in your career?

Introduction

Cryptography is a method to achieve confidentiality among mutually trusted people and organizations. The messages are sent via an unsecured network with no proper security. If we do not use Cryptography to encrypt the messages, it may hamper the confidentiality of the text.

notion of cryptography

In this blog, we will detail several aspects of one of the most important algorithms for discrete logarithms- Shank’s Algorithm. We will also see an example of Shank’s Algorithm to understand it better.

Shank’s Algorithm

Shank’s Algorithm is the first non-trivial algorithm that performs a time-memory trade-off. It is used in modular arithmetic to solve for r in the form r2 ≡ n (mod p)

where p is prime, and r is the square root of n modulo p.

shank's not sharks

Shank’s Algorithm constructs two lists of size √n and then search for a collision. This is because collision helps the required discrete logarithm to be calculated. It solves ECDLP problems comparatively faster than brute or naive approaches. However, its time complexity is exponential such,

O(√m) = O(√n) = O(√p)

Also, it requires O(√p) storage. 

The Shank’s Algorithm Function

SHANK’S(G, x, α, β)

1. m ← Γ√ x⅂

2. for j ← 0 to m−1

         do calculate αmj

3. Sort the m-ordered pairs (j, αmj) concerning only the second coordinates, getting a list L1.

4. for i ← 0 to m−1

        do calculate βα−i

5. Sort the m-ordered pairs (i, βα−i) concerning only the second coordinates, getting a list L2.

6. Search for a pair (j, y) ∈ L1 and a pair (i, y) ∈ L2

That is, find two pairs having identical second coordinates.

7. logαβ ← (mj + i) mod x

Proof

Suppose f (j, y) ∈ L1 and (i, y) ∈ L2, then

αmj = y = βα−i,

So

αmj+i = β.

Conversely, for any β ∈〈α〉, we have 0 ≤ logαβ ≤ x−1. If we divide logαβ by the calculated integer m, we can express logαβ in the form

logαβ = mj + i,

where 0 ≤ j, i ≤ m−1. The equation j ≤ m − 1 stands because

logαβ ≤ n−1 ≤ m2−1 = m(m−1) + m−1.

Therefore, the search in step 6 will be successful. However, if β ∉〈α〉, then step 6 will not be successful. Here is a small example to illustrate Shank’s Algorithm.

Example

Here is a simple example to illustrate Shank’s Algorithm.

Suppose we wish to find log3525 in (Z809 ∗, ·). Keep in mind that 809 is a prime integer and 3 is a primitive element in Z809 ∗, so we have n = 808, α = 3, β = 525, and m =  Γ√ 808⅂ = 29. Then

α29 mod 809 = 99.

Firstly, we will compute the ordered pairs (j, 99j mod 809) for 0 ≤ j ≤ 28. Then, obtain the list containing following pairs:

(0, 1) (2, 93) (3, 308) (5, 329) (4, 559)

(6, 211) (7, 664) (8, 207) (10, 644) (1, 99)

(9, 268) (11, 654) (12, 26) (13, 147) (15, 727)

(14, 800)(16, 781) (17, 464) (18, 632) (20, 528) 

(19, 275) (21, 496) (22, 564) (23, 15) (25, 586)

(24, 676) (26, 575) (27, 295) (28, 81)

This list is then ordered as required to produce the first list, L1.

The second list contains some ordered pairs (i, 525 × (3i)−1 mod 809), while 0 ≤ j ≤ 28.

The list we obtain is as follows:

(0, 525) (1, 175) (2, 328) (3, 379) (5, 132)

(4, 396) (6, 44) (7, 554) (8, 724) (10, 440) 

(9, 511)(11, 686) (12, 768) (13, 256) (15, 388)

(14, 355)(16, 399) (17, 133) (18, 314) (20, 754)

(19, 644) (21, 521) (22, 713) (23, 777) (25, 356)

(24, 259) (26, 658) (27, 489) (28, 163)

After sorting this list, we get L2.

If we proceed simultaneously through both the two sorted lists searching for a common second coordinate, we came to know that (10, 644) is present in L1 and (19, 644) is in L2. So, we can calculate log3525.

log3525 = (29 × 10 + 19) mod 808

             = 309

As a final verification, we can calculate that 3309 ≡ 525 (mod 809).

Frequently Asked Questions

Differentiate Plain Text and Cipher Text.

Plain Text is a simple text that any normal human can read. However, Cipher Text is an encrypted text that can only be read and not understood.

Why do we use Session Key?

A Session key is an encrypted use-only-once key that can be sent with every message. It protects communications among computers, users, clients, and servers.

Describe the Blind Signature Scheme.

The phenomenon of hiding the message’s content of digital signature before it is signed is known as Blind Signature Scheme. This happens when message author and signer are complete different stakeholders.

Mention the importance of Encryption.

Encryption ensures the conversation’s privacy and confidentiality. We frequently use Encryption when there is a need to secure the data such as financial statements, test results, or important documents.

Conclusion

Overall, we understood several aspects of one most important algorithms for discrete logarithms- Shank’s Algorithm in detail. We will also see an example of Shank’s Algorithm to understand it better. 

We hope the above discussion helped you understand the concepts of one most important algorithms for discrete logarithms- Shank’s Algorithm in Cryptography and can be used for future reference whenever needed. To learn more about Cryptography, you can refer to blogs on Security in CryptographySigning and Encrypting in CryptographyAuthenticated Encryption in CryptographyCBC MAC in Cryptography, and Message Authentication Codes in Cryptography.

Visit our website to read more such blogs. Make sure you enroll in our courses, take mock tests, solve problems, and interview puzzles. Also, you can pay attention to interview stuff- interview experiences and an interview bundle for placement preparations. Do upvote our blog to help fellow ninjas grow.

Happy Coding!

Live masterclass