104 lines
3.0 KiB
Erlang
104 lines
3.0 KiB
Erlang
%%% @author Tony Wallace <tony@tony.gen.nz>
|
|
%%% @doc
|
|
%%% For details of the algorithms used see
|
|
%%% https://en.wikipedia.org/wiki/Modular_exponentiation
|
|
%%% @end
|
|
%%% Created : 21 Jul 2021 by Tony Wallace <tony@resurrection>
|
|
|
|
-module mod.
|
|
-export [mod_mult/3,mod_exp/3,binary_exp/2,test/0].
|
|
|
|
mod_mult(I1,I2,Mod) when
|
|
I1 > Mod,
|
|
is_integer(I1), is_integer(I2), is_integer(Mod) ->
|
|
mod_mult(I1 rem Mod,I2,Mod);
|
|
mod_mult(I1,I2,Mod) when
|
|
I2 > Mod,
|
|
is_integer(I1), is_integer(I2), is_integer(Mod) ->
|
|
mod_mult(I1,I2 rem Mod,Mod);
|
|
mod_mult(I1,I2,Mod) when
|
|
is_integer(I1), is_integer(I2), is_integer(Mod) ->
|
|
(I1 * I2) rem Mod.
|
|
|
|
mod_exp(Base,Exp,Mod) when
|
|
is_integer(Base),
|
|
is_integer(Exp),
|
|
is_integer(Mod),
|
|
Base > 0,
|
|
Exp > 0,
|
|
Mod > 0 ->
|
|
binary_exp_mod(Base,Exp,Mod);
|
|
mod_exp(_,0,_) -> 1.
|
|
|
|
|
|
binary_exp(Base,Exponent) when
|
|
is_integer(Base),
|
|
is_integer(Exponent),
|
|
Base > 0,
|
|
Exponent > 0 ->
|
|
binary_exp(Base,Exponent,1);
|
|
binary_exp(_,0) ->
|
|
1.
|
|
|
|
binary_exp(_,0,Result) ->
|
|
Result;
|
|
binary_exp(Base,Exponent,Acc) ->
|
|
binary_exp(Base*Base,Exponent bsr 1,Acc * exp_factor(Base,Exponent)).
|
|
|
|
|
|
binary_exp_mod(Base,Exponent,Mod) ->
|
|
binary_exp_mod(Base rem Mod,Exponent,Mod,1).
|
|
binary_exp_mod(_,0,_,Result) ->
|
|
Result;
|
|
binary_exp_mod(Base,Exponent,Mod,Acc) ->
|
|
binary_exp_mod((Base*Base) rem Mod,
|
|
Exponent bsr 1,Mod,(Acc * exp_factor(Base,Exponent))rem Mod).
|
|
|
|
exp_factor(_,0) ->
|
|
1;
|
|
exp_factor(Base,1) ->
|
|
Base;
|
|
exp_factor(Base,Exponent) ->
|
|
exp_factor(Base,Exponent band 1).
|
|
|
|
test() ->
|
|
445 = mod_exp(4,13,497),
|
|
%% Rosetta code example:
|
|
R = 1527229998585248450016808958343740453059 =
|
|
mod_exp(2988348162058574136915891421498819466320163312926952423791023078876139,
|
|
2351399303373464486466122544523690094744975233415544072992656881240319,
|
|
binary_exp(10,40)),
|
|
R.
|
|
|
|
%%%-------------------------------------------------------------------
|
|
%%% @author Tony Wallace <tony@tony.gen.nz>
|
|
%%% @doc
|
|
%%% Blocking not implemented. Runtime exception if message too long
|
|
%%% Not a practical issue as RSA usually limited to symmetric key exchange
|
|
%%% However as a key exchange tool no advantage in compressing plaintext
|
|
%%% so that is not done either.
|
|
%%% @end
|
|
%%% Created : 24 Jul 2021 by Tony Wallace <tony@resurrection>
|
|
%%%-------------------------------------------------------------------
|
|
|
|
-module rsa.
|
|
-export([key_gen/2,encrypt/2,decrypt/2,test/0]).
|
|
-type key() :: {integer(),integer()}.
|
|
key_gen({N,D},E) ->
|
|
{{E,N},{D,N}}.
|
|
-spec encrypt(key(),integer()) -> integer().
|
|
encrypt({E,N},MessageInt)
|
|
when MessageInt < N ->
|
|
mod:mod_exp(MessageInt,E,N).
|
|
-spec decrypt(key(),integer()) -> integer().
|
|
decrypt({D,N},Message) ->
|
|
mod:mod_exp(Message,D,N).
|
|
test() ->
|
|
PlainText=10722935,
|
|
N = 9516311845790656153499716760847001433441357,
|
|
E = 65537,
|
|
D = 5617843187844953170308463622230283376298685,
|
|
{PublicKey,PrivateKey} = key_gen({N,D},E),
|
|
PlainText =:= decrypt(PrivateKey,
|
|
encrypt(PublicKey,PlainText)).
|