ctfnote
  • /home/ret2basic.eth
  • Game Hacking
    • โœ…C++
    • Ghidra
    • Cheat Engine
    • Proxy
    • DLL injection
    • Keygen
    • Aimbot
  • Web3 Security Research
    • ๐Ÿ‘‘Web3 Security Research Trivia
    • โœ…Solidity
      • โœ…Mastering Ethereum
      • โœ…Storage
      • โœ…Memory
      • โœ…Calldata
      • โœ…ABI
    • โœ…Foundry
      • โœ…Introduction
      • โœ…How to Write Basic Tests
      • โœ…Set Soliditiy Compiler Version
      • โœ…Remappings
      • โœ…Auto Format Code
      • โœ…Console Log
      • โœ…Authentication
      • โœ…Error
      • โœ…Event
      • โœ…Time
      • โœ…Send ETH
      • โœ…Signature
      • โœ…Fork
      • โœ…Mint 1 Million DAI on Mainnet Fork
      • โœ…FFI
      • โœ…Fuzz
      • โœ…Invariant Testing - Part 1
      • Invariant Testing - Part 2
      • Invariant Testing - Part 3
      • Differential Test
    • โœ…Secureum
      • โœ…Epoch 0
        • โœ…Slot 1: Ethereum 101
          • โœ…Notes
          • โœ…Ethereum Whitepaper
          • โœ…Extra Study: What happens when you send 1 DAI
          • โœ…Quiz
        • โœ…Slot 2: Solidity 101
          • โœ…Notes
          • โœ…OpenZeppelin ERC20
          • โœ…OpenZeppelin ERC721
          • โœ…OpenZeppelin Ownable
          • โœ…OpenZeppelin Pausable
          • โœ…OpenZeppelin ReentrancyGuard
          • โœ…Quiz
        • โœ…Slot 3: Solidity 201
          • โœ…Notes
          • โœ…OpenZeppelin SafeERC20
          • โœ…OpenZeppelin ERC-777
          • โœ…OpenZeppelin ERC-1155
          • โœ…OpenZeppelin ERC-3156
          • โœ…OpenZeppelin - Proxy Upgrade Pattern
          • โœ…Quiz
        • โœ…Slot 4: Pitfalls and Best Practices 101
          • โœ…Notes
          • โœ…Intro to Security First Development
          • โœ…Quiz
        • โœ…Slot 5: Pitfalls and Best Practices 201
          • โœ…Notes
          • So you want to use a price oracle
          • The Dangers of Surprising Code
          • โœ…Quiz
        • โœ…Slot 6: Auditing Techniques & Tools 101
          • โœ…Notes
          • โœ…Quiz
        • โœ…Slot 7: Audit Findings 101
          • Notes
          • โœ…Fei Protocol - ConsenSys
          • โœ…Uniswap V3 - Trail of Bits
          • โœ…Chainlink - Sigma Prime
          • โœ…Opyn Gamma - OpenZeppelin
          • โœ…Quiz
        • โœ…Slot 8: Audit Findings 201
          • Notes
          • 1inch Liquidity - Consensus
          • Original Dollar - Trail of Bits
          • Synthetix EtherCollateral - Sigma Prime
          • Holdefi - OpenZeppelin
          • Quiz
      • โœ…Epoch โˆž
        • โœ…RACE #4 - ERC20 Implementation
        • โœ…RACE #5 - ERC1155 Implementation
        • โœ…RACE #6 - ERC721 Application
        • โœ…RACE #7 - Bored Ape
        • โœ…RACE #8 - ERC721 Roles
        • โœ…RACE #9 - Proxy
        • โœ…RACE #10 - Test Cases
        • โœ…RACE #11 - Staking
        • โœ…RACE #12 - ERC20 Permit
        • โœ…RACE #13 - ERC20 with Callback
        • โœ…RACE #14 - Lending
        • โœ…RACE #15 - DEX
        • โœ…RACE #16 - Flash Loan
        • โœ…RACE #17
    • DeFi
      • Glossary
        • TWAP vs. VWAP
        • Tranches
      • DeFi MOOC
        • Lecture 2: Introduction to Blockchain Technologies
        • Lecture 5: DEX
        • Lecture 6: Decentralized Lending
        • Lecture 10: Privacy on the Blockchain
        • Lecture 12: Practical Smart Contract Security
        • Lecture 13: DeFi Security
      • Uniswap V2
      • Compound V3
        • โœ…Whitepaper
        • โœ…Interacting with Compound
          • โœ…Supply and Redeem
          • โœ…Borrow and Repay
          • โœ…Liquidation
          • โœ…Long and Short
        • โœ…Interest Model
        • CToken
      • Aave
      • Chainlink
        • โœ…Getting Started
        • โœ…Data Feeds
        • โœ…VRF
      • Optimism
        • Bedrock
      • LayerZero
      • Opensea
        • Seaport
    • EVM
      • โœ…Andreas Antonopoulos - The Ethereum Virtual Machine
      • โœ…Program The Blockchain - Smart Contract Storage
      • โœ…EVM Codes - EVM Playground for Opcodes
      • โœ…Fvictorio - EVM Puzzles
      • โœ…Daltyboy11 - More EVM Puzzles
      • โœ…EVM Through Huff
      • Noxx - EVM Deep Dives
      • โœ…Jordan McKinney - EVM Explained
      • Openzepplin - Deconstructing a Solidity Contract
      • Jeancvllr - EVM Assembly
      • Peter Robinson - Solidity to Bytecode, Memory & Storage
      • Marek Kirejczyk - Ethereum Under The Hood
      • โœ…Official Solidity Docs
      • Dissecting EVM using go-ethereum Eth client implementation - deliriusz.eth
    • Vulnerabilities
      • Rounding Issues
        • Kyberswap
      • Bridges
      • Governance / Voting Escrows
      • Bizzare Bug Classes
        • TIME - ERC2771Context + Multicall calldata manipulation
    • Fancy Topics
      • Vulnerabilities SoK
        • โœ…Demystifying Exploitable Bugs in Smart Contracts
        • Blockchain Hacking Techniques 2022 Top 10 - Todo
      • yAcademy
        • Proxies
          • yAcademy - Proxy Basics
          • yAcademy - Proxies Deep Dive
          • yAcademy - Security Guide to Proxy Vulns
        • defi-fork-bugs
      • Spearbit
        • โœ…Community Workshop: Riley Holterhus
        • Economic Security with fmrmf
        • Numerical Analysis for DeFi Audits: A TWAMM Case Study by Kurt Barry
  • Red Teaming
    • โœ…Enumeration
      • Service Enumeration
        • SMTP (Port 25)
        • Samba (Port 139, 445)
        • SNMP (Port 161,162,10161,10162)
        • rsync (Port 873)
        • NFS (Port 2049)
        • Apache JServ Protocol (Port 8081)
        • NetBIOS
      • Nmap
      • Gobuster / Feroxbuster / FUFF / Wfuzz
      • Drupal
    • โœ…Exploitation
      • Public Exploits
      • PHP Webshells
      • Reverse Shell
      • TTY
      • File Transfer
      • Metasploit
      • Password Spray
    • โœ…Buffer Overflow
      • Step 0: Spiking (Optional)
      • Step 1: Fuzzing
      • Step 2: Finding the Offset
      • Step 3: Overwriting the EIP
      • Step 4: Finding Bad Characters
      • Step 5: Finding the Right Module
      • Step 6: Generating Shellcode and Gaining Root
    • โœ…Privilege Escalation
      • Linux Privilege Escalation
        • Linux Permissions
        • Manual Enumeration
        • Automated Tools
        • Kernel Exploits
        • Passwords and File Permissions
        • SSH Keys
        • Sudo
        • SUID
        • Capabilities
        • Cron Jobs
        • NFS Root Squashing
        • Docker
        • GNU C Library
        • Exim
        • Linux Privilege Escalation Course Capstone
      • Windows Privilege Escalation
        • Manual Enumeration
        • Automated Tools
        • Kernel Exploits
        • Passwords and Port Forwarding
        • WSL
        • Token Impersonation and Potato Attacks
        • Meterpreter getsystem
        • Runas
        • UAC Bypass
        • Registry
        • Executable Files
        • Startup Applications
        • DLL Hijacking
        • Service Permissions (Paths)
        • CVE-2019-1388
        • HiveNightmare
        • Bypass Space Filter
    • โœ…Post Exploitation
      • Linux Post Exploitation
        • Add a User
        • SSH Key
      • Windows Post Exploitation
        • windows-resources
        • Add a User
        • RDP
    • โœ…Pivoting
      • Windows: Chisel
      • Linux: sshuttle
    • Active Directory (AD)
      • Initial Compromise
        • HTA Phishing
        • VBA Macro Phishing
        • LLMNR Poisoning
        • SMB Relay
        • GPP / cPassword
      • Domain Enumeration
        • Manual Enumeration
        • PowerView
        • BloodHound
      • Lateral Movement
        • PsExec
        • WMI
        • Runas
        • Pass the Hash
        • Overpass the Hash
        • Pass the Ticket
      • Kerberos
        • Kerberoast
        • AS-REP Roast
      • MS SQL Server
    • Command & Control (C2)
      • Cobalt Strike
        • Bypassing Defences
          • Artifact Kit
          • Resource Kit
          • AMSI Bypass
          • PowerPick
        • Extending Cobalt Strike
          • Elevate Kit
          • Malleable C2 Profile
      • Metasploit
        • Payloads
        • Post Exploitation
        • Automation
      • C2 Development
    • Malware Development
      • "Hot Dropper"
      • PE Format
        • Overview
      • Process Injection
      • Reflective DLL
      • x86 <=> x64
      • Hooking
      • VeraCry
      • Offensive C#
      • AV Evasion
        • AV Evasion with C# and PowerShell
        • AMSI Bypass
  • Cryptography
    • Hash Functions
    • MAC
    • AES
      • Byte at a Time
      • CBC CCA
      • CBC Bit Flipping
      • CBC Padding Oracle
    • Diffie-Hellman
    • RSA
      • Prime Factors
      • Multiple Ciphertexts
      • Low Public Exponent
      • Low Private Exponent
    • ECC
    • Digital Signature
    • JWT
    • PRNG
    • SSL/TLS
    • Research
      • โœ…Lattice-based Cryptography (Lattice)
      • Elliptic Curve Cryptography (ECC)
      • Oblivious Transfer (OT)
      • Secure Multi-party Computation (MPC)
      • Learning with Error (LWE)
      • Fully Homomorphic Encryption (FHE)
      • Zero Knowledge Proof (ZKP)
      • Oblivious RAM (ORAM)
  • Computer Science
    • Linux
      • Setup
      • curl
      • Hard Link vs. Symlink
      • Man Page
      • /dev/null
    • Python
      • New Features
      • Operators, Expressions, and Data Manipulation
      • Program Structure and Control Flow
      • Objects, Types, and Protocols
      • Functions 101
      • Generators
      • Classes and Object-Oriented Programming
      • Memory Management
      • Concurrency and Parallelism
        • Multithreading and Thread Safety
        • Asynchronization
        • Multiprocessing
        • Global Interpreter Lock (GIL)
      • Built-in Functions and Standard Library
        • import collections
        • import itertools
        • import sys
        • import re
        • import pickle
        • import json
      • Third-party Library
        • from pwn import *
        • import requests
        • from bs4 import BeautifulSoup
        • from scapy.all import *
        • py2exe
    • HTML, CSS, JavaScript, and React
      • HTML
      • CSS
      • JavaScript
        • var vs. let
        • Objects
        • Arrays
        • Functions
        • Modules
        • Asynchronous JavaScript
      • React
    • Data Structures and Algorithms
      • Binary Search
    • The Linux Programming Interface
      • Processes
        • Memory Allocation
        • The Process API
        • Process Creation
        • Process Termination
        • Monitoring Child Processes
        • Program Execution
      • Signals
      • Threads
        • Thread Synchronization
        • Thread Safety and Pre-Thread Storage
      • IPC
        • Pipes and FIFOs
        • Memory Mappings
        • Virtual Memory Operations
      • Sockets
    • Computer Systems
      • Hexadecimal
      • Signedness
      • Registers
      • Instructions
      • Syscall
      • Process Memory
      • Stack Frame
      • Preemptive Multitasking
      • IPC
      • Threads
    • Databases
      • MySQL
        • Basic Syntax
        • Data Types
        • Modifying Tables
        • Duplicating and Deleting
        • SELECT
        • Transaction
      • GraphQL
    • Distributed Systems
      • Introduction
        • What is a Distributed System?
        • Design Goals
        • Scaling Techniques
        • Types of Distributed Systems
      • Architecture
        • System Architectures
        • Example Architectures
      • Communication
        • Foundations
        • Remote Procedure Call
        • Message-oriented Communication
      • Coordination
        • Clock Synchronization
        • Logical Clock
      • Consistency and Replication
        • Introduction
        • Data-centric Consistency
        • Client-centric Consistency
    • Static Analysis
      • Intermediate Representation
      • Data Flow Analysis
      • Interprocedural Analysis
      • Pointer Analysis
      • Static Analysis for Security
      • Datalog-Based Program Analysis
      • Soundness and Soundiness
      • CFL-Reachability and IFDS
  • Web
    • โœ…Prerequisites
      • OWASP Top 10
        • 1. Broken Access Control
        • 2. Cryptographic Failures
        • 3. Injection
        • 4. Insecure Design
        • 5. Security Misconfiguration
        • 6. Vulnerable and Outdated Components
        • 7. Identification and Authentication Failures
        • 8. Software and Data Integrity Failures
        • 9. Security Logging and Monitoring Failures
        • 10. SSRF
      • HTTP
        • HTTP Status Codes
        • HTTP Headers
      • Burp Suite
        • Burp Intruder
        • Burp Extender
        • Burp Collaborator
      • Information Gathering
        • DNS
        • Git
        • Editor
        • Server
      • Bug Bounty Report Writing
    • File Upload
      • Webshell
      • IIS, Nginx, and Apache Vulnerabilities
      • .htaccess (Apache) / web.config (IIS)
      • Alternate Data Stream
      • Code Review: bWAPP Unrestricted File Upload
    • SQL Injection (SQLi)
      • Cheat Sheet
      • UNION Attacks
      • Examining the Database
      • Blind SQL Injection
      • WAF Bypass
      • Out-Of-Band (OOB)
      • Webshell and UDF
      • sqlmap
        • Code Review: Initialization
        • Code Review: tamper
    • Cross-Site Scripting (XSS)
      • Cheat Sheet
      • Reflected XSS
      • Stored XSS
      • DOM-Based XSS
      • XSS Contexts
      • CSP
    • CSRF and SSRF
      • Client-Side Request Forgery (CSRF)
        • XSS vs. CSRF
        • CSRF Tokens and SameSite Cookies
      • Server-Side Request Forgery (SSRF)
        • Attacks
        • Bypassing Restrictions
        • SSRF + Redis
    • XML External Entities (XXE)
    • Insecure Deserialization
      • Python Deserialization
      • PHP Deserialization
      • Java Deserialization
        • Shiro
        • FastJSON
        • WebLogic
    • HTTP Request Smuggling
    • OS Command Injection
      • Whitespace Bypass
      • Blacklist Bypass
      • Blind OS Command Injection
      • Lab 1: HITCON 2015 BabyFirst
      • Lab 2: HITCON 2017 BabyFirst Revenge
      • Lab 3: HITCON 2017 BabyFirst Revenge v2
    • โœ…Directory Traversal
    • HTTP Parameter Pollution
    • Server-Side Template Injection (SSTI)
    • LDAP Injection
    • Redis
      • Authentication
      • RCE
      • Mitigations
  • Pwn
    • Linux Exploitation
      • Protections
      • Shellcoding
        • Calling Convention
        • Null-free
        • Reverse Shell
        • ORW
      • ROP
        • Stack Alignment
        • ret2text
        • ret2syscall
        • ret2libc
        • ret2csu
        • BROP
        • SROP
        • Stack Pivot
      • ptmalloc
        • chunks
        • malloc() and free()
        • bins
        • tcache
      • UAF
      • Race Conditions
        • TOCTTOU
        • Dirty Cow
        • Meltdown
        • Spectre
      • Kernel
      • Appendix: Tools
        • socat
        • LibcSearcher-ng
        • OneGadget
    • Windows Exploitation
      • Classic
      • SEH
      • Egghunting
      • Unicode
      • Shellcoding
      • ROP
      • Appendix: Tools
        • ImmunityDbg
        • Mona.py
    • Fuzzing
      • AFL++
        • Quickstart
        • Instrumentation
        • ASAN
        • Code Coverage
        • Dictionary
        • Parallelization
        • Partial Instrumentation
        • QEMU Mode
        • afl-libprotobuf-mutator
      • WinAFL
      • Fuzzilli
  • Reverse
    • Bytecode
      • Python Bytecode
    • ๐Ÿ‘‘Z3 solver
    • angr
      • angr Template
Powered by GitBook
On this page
  • Elliptic Curve
  • Arithmetics on Elliptic Curves
  • Point Negation
  • Point Addition
  • Scalar Multiplication
  • Curves and Logs
  • Algorithm
  • Implementation
  • Lab
  • Reference

Was this helpful?

  1. Cryptography

ECC

Elliptic Curve Cryptography

PreviousLow Private ExponentNextDigital Signature

Last updated 3 years ago

Was this helpful?

Elliptic Curve

An elliptic curve is a plane curve defined by an equation of the form:

y2=x3+ax+by^{2}=x^{3}+ax+by2=x3+ax+b

after a linear change of variables (aaa and bbb are real numbers). This type of equation is called a Weierstrass equation.

The definition of elliptic curve also requires that the curve is non-singular. Geometrically, this means that the graph has no cusps, self-intersections, or isolated points. Algebraically, this holds if and only if the discriminant:

ฮ”=โˆ’16(4a3+27b2)\Delta =-16(4a^{3}+27b^{2})ฮ”=โˆ’16(4a3+27b2)

is not equal to zero. (Although the factor โˆ’16 is irrelevant to whether or not the curve is non-singular, this definition of the discriminant is useful in a more advanced study of elliptic curves.)

The (real) graph of a non-singular curve has two components if its discriminant is positive, and one component if it is negative. For example, in the graphs shown in figure below, the discriminant in the first case is 64, and in the second case is โˆ’368:

Arithmetics on Elliptic Curves

Point Negation

Algorithm

Implementation

Point Addition

Algorithm

  1. Otherwise:

Implementation

#!/usr/bin/env python3
from Crypto.Util.number import inverse

#--------Data--------#

a = 497
b = 1768
p = 9739

P = (493, 5564)
Q = (1539, 4742) 
R = (4403,5202)

#--------Addition--------#

def point_addition(P, Q):
    # Define zero
    O = (0, 0)

    # If P = O, then P + Q = Q
    if P == O:
        return Q
    # If Q = O, then P + Q = P
    if Q == O:
        return P

    # Otherwise, write P = (x1, y1) and Q = (x2, y2)
    x1, y1 = P[0], P[1]
    x2, y2 = Q[0], Q[1]

    # If x1 = x2 and y1 = -y2, then P + Q = O
    if x1 == x2 and y1 == -y2:
        return O

    # Otherwise, if P โ‰  Q: ฮป = (y2 - y1) / (x2 - x1)
    if P != Q:
        lam = ((y2 - y1) * inverse(x2 - x1, p)) % p
    # If P = Q: ฮป = (3 * x1**2 + a) / 2 * y1
    else:
        lam = ((3 * x1**2 + a) * inverse(2 * y1, p)) % p

    # x3 = ฮป**2 - x1 - x2, y3 = ฮป *( x1 - x3) - y1
    x3 = (lam**2 - x1 - x2) % p
    y3 = (lam * (x1 - x3) - y1) % p

    # P + Q = (x3, y3)
    summation = (x3, y3)

    return summation

#--------Testing--------#

# X = (5274, 2841) 
# Y = (8669, 740)
# print(point_addition(X, Y))
# print(point_addition(X, X))

# S = P + P + Q + R
S = point_addition(point_addition(point_addition(P, P), Q), R)
print(S)

Scalar Multiplication

Algorithm

Implementation

#!/usr/bin/env python3
from Crypto.Util.number import inverse

#--------Data--------#

a = 497
b = 1768
p = 9739

P = (2339, 2213)

#--------Functions--------#

def point_addition(P, Q):
    # Define zero
    O = (0, 0)

    # If P = O, then P + Q = Q
    if P == O:
        return Q
    # If Q = O, then P + Q = P
    if Q == O:
        return P

    # Otherwise, write P = (x1, y1) and Q = (x2, y2)
    x1, y1 = P[0], P[1]
    x2, y2 = Q[0], Q[1]

    # If x1 = x2 and y1 = -y2, then P + Q = O
    if x1 == x2 and y1 == -y2:
        return O

    # Otherwise, if P โ‰  Q: ฮป = (y2 - y1) / (x2 - x1)
    if P != Q:
        lam = ((y2 - y1) * inverse(x2 - x1, p)) % p
    # If P = Q: ฮป = (3 * x1**2 + a) / 2 * y1
    else:
        lam = ((3 * x1**2 + a) * inverse(2 * y1, p)) % p

    # x3 = ฮป**2 - x1 - x2, y3 = ฮป *( x1 - x3) - y1
    x3 = (lam**2 - x1 - x2) % p
    y3 = (lam * (x1 - x3) - y1) % p

    # P + Q = (x3, y3)
    summation = (x3, y3)

    return summation

def scalar_multiplication(n, P):
    # Define zero
    O = (0, 0)
    # Set Q = P and R = O
    Q, R = P, O

    while n > 0:
        # If n โ‰ก 1 mod 2, set R = R + Q
        if n % 2 == 1:
            R = point_addition(R, Q)
        # Set Q = 2 Q and n = โŒŠn/2โŒ‹.
        Q = point_addition(Q, Q)
        n //= 2

    return R

#--------Testing--------#

# X = (5323, 5438)
# print(scalar_multiplication(1337, X))

# Q = 7863 P
print(scalar_multiplication(7863, P))

Curves and Logs

Algorithm

Implementation

#!/usr/bin/env python3
from Crypto.Util.number import inverse
from hashlib import sha1

#--------Data--------#

a = 497
b = 1768
p = 9739

G = (1804,5368)
Q_A = (815, 3190)
n_B = 1829

#--------Functions--------#

def point_addition(P, Q):
    # Define zero
    O = (0, 0)

    # If P = O, then P + Q = Q
    if P == O:
        return Q
    # If Q = O, then P + Q = P
    if Q == O:
        return P

    # Otherwise, write P = (x1, y1) and Q = (x2, y2)
    x1, y1 = P[0], P[1]
    x2, y2 = Q[0], Q[1]

    # If x1 = x2 and y1 = -y2, then P + Q = O
    if x1 == x2 and y1 == -y2:
        return O

    # Otherwise, if P โ‰  Q: ฮป = (y2 - y1) / (x2 - x1)
    if P != Q:
        lam = ((y2 - y1) * inverse(x2 - x1, p)) % p
    # If P = Q: ฮป = (3 * x1**2 + a) / 2 * y1
    else:
        lam = ((3 * x1**2 + a) * inverse(2 * y1, p)) % p

    # x3 = ฮป**2 - x1 - x2, y3 = ฮป *( x1 - x3) - y1
    x3 = (lam**2 - x1 - x2) % p
    y3 = (lam * (x1 - x3) - y1) % p

    # P + Q = (x3, y3)
    summation = (x3, y3)

    return summation

def scalar_multiplication(n, P):
    # Define zero
    O = (0, 0)
    # Set Q = P and R = O
    Q, R = P, O

    # Loop while n > 0
    while n > 0:
        # If n โ‰ก 1 mod 2, set R = R + Q
        if n % 2 == 1:
            R = point_addition(R, Q)
        # Set Q = 2 Q and n = โŒŠn/2โŒ‹.
        Q = point_addition(Q, Q)
        n //= 2

    return R

#--------ECDH--------#

S = scalar_multiplication(n_B, Q_A)
key = sha1(str(S[0]).encode()).hexdigest()

print(key)

Lab

Reference

The rule is: if P=(xP,yP)P = (x_P,y_P)P=(xPโ€‹,yPโ€‹), then P+(xP,xP+yP)=OP + (x_P, x_P+y_P) = OP+(xPโ€‹,xPโ€‹+yPโ€‹)=O. In other word, โˆ’P=(xP,xP+yP)-P = (x_P, x_P+y_P)โˆ’P=(xPโ€‹,xPโ€‹+yPโ€‹).

In this challenge we are given P=(8045,6936)P = (8045, 6936)P=(8045,6936), hence Q=โˆ’P=(8045,(8045+6936)modโ€‰โ€‰9739)=(8045,2803)Q = -P = (8045, (8045 + 6936) \mod 9739) = (8045, 2803)Q=โˆ’P=(8045,(8045+6936)mod9739)=(8045,2803)

If P=OP = OP=O, then P+Q=QP + Q = QP+Q=Q.

Otherwise, if Q=OQ = OQ=O, then P+Q=PP + Q = PP+Q=P.

Otherwise, write P=(x1,y1)P = (x_1, y_1)P=(x1โ€‹,y1โ€‹) and Q=(x2,y2)Q = (x_2, y_2)Q=(x2โ€‹,y2โ€‹).

If x1=x2x_1 = x_2x1โ€‹=x2โ€‹ and y1=โˆ’y2y_1 = โˆ’y_2y1โ€‹=โˆ’y2โ€‹, then P+Q=OP + Q = OP+Q=O.

if Pโ‰ QP \neq QP๎€ =Q: ฮป=(y2โˆ’y1)/(x2โˆ’x1)\lambda = (y_2 - y_1) / (x_2 - x_1)ฮป=(y2โ€‹โˆ’y1โ€‹)/(x2โ€‹โˆ’x1โ€‹)

if P=QP = QP=Q: ฮป=(3x12+a)/2y1\lambda = (3x_1^2 + a) / 2y_1ฮป=(3x12โ€‹+a)/2y1โ€‹

x3=ฮป2โˆ’x1โˆ’x2x_3 = \lambda_2 โˆ’ x_1 โˆ’ x2x3โ€‹=ฮป2โ€‹โˆ’x1โ€‹โˆ’x2 and y3=ฮป(x1โˆ’x3)โˆ’y1y_3 = \lambda(x_1 โˆ’ x_3) โˆ’ y_1y3โ€‹=ฮป(x1โ€‹โˆ’x3โ€‹)โˆ’y1โ€‹

P+Q=(x3,y3)P + Q = (x_3, y_3)P+Q=(x3โ€‹,y3โ€‹)

Input: PPP in E(Fp)E(F_p)E(Fpโ€‹) and an integer n>0n > 0n>0.

Set Q=PQ = PQ=P and R=OR = OR=O.

Loop while n>0n > 0n>0.

If nโ‰ก1modโ€‰โ€‰2n \equiv 1 \mod 2nโ‰ก1mod2, set R=R+QR = R + QR=R+Q.

Set Q=2QQ = 2QQ=2Q and n=โŒŠn/2โŒ‹n = \left\lfloor n/2 \right\rfloorn=โŒŠn/2โŒ‹.

If n>0n > 0n>0, continue with loop at Step 2.

Return the point RRR, which equals nPnPnP.

Alice and Bob agree on a curve EEE, a prime ppp and a generator point GGG.

Alice generates a secret random integer nAn_AnAโ€‹ and calculates QA=nAGQ_A = n_AGQAโ€‹=nAโ€‹G.

Bob generates a secret random integer nBn_BnBโ€‹ and calculates QB=nBGQ_B = n_BGQBโ€‹=nBโ€‹G.

Alice sends Bob QAQ_AQAโ€‹, and Bob sends Alice $$Q_B$$. Due to the hardness of ECDLP, an onlooker Eve is unable to calculatenA/B n{A/B}nA/B in reasonable time.

Alice then calculates nAQBn_AQ_BnAโ€‹QBโ€‹, and Bob calculates nBQAn_BQ_AnBโ€‹QAโ€‹.

Due to the associativity of scalar multiplication, S=nAQB=nBQAS = n_AQ_B = n_BQ_AS=nAโ€‹QBโ€‹=nBโ€‹QAโ€‹. Alice and Bob can use SSS as their shared secret.

CryptoHack โ€“ Elliptic Curves challengesCryptoHack
Elliptic Curves - CryptoHack
CryptoHack โ€“ Elliptic Curves challengesCryptoHack
Elliptic Curves - CryptoHack
Elliptic curveWikipedia
Elliptic curve - Wikipedia
ECC2 (200) ยท Hackademia Writeups
picoCTF 2017 ECC 2 - 200 (Cryptography) Writeup
Logo
Logo
Logo
Graphs of curves y^2 = x^3 โˆ’ x and y^2 = x^3 โˆ’ x + 1
Logo