musig – Schnorr without R in the challenge

I read the Schnorr and MuSig papers and stumbled over the problem that the use of deterministic nonces in multisignatures is not safe. The adversary would be able to extract the private key from the victim, if he initiates a second signing session with the victim on the same message, but changes his own public nonce.
This happens, because this changes also the partial signature of the victim. (s = r + c*x)
The challenge is constructed in this way : c=H(R||m) (not key-prefixed version).

I’m wondering, would the exclusion of the public nonce from the H-sig challenge not result in a constant signature of all signers and therefore allow the use of deterministic nonces? The challenge could be c=H(m) or c=H(P||m).
Why is R (public nonce) in the first place included inside the hash function? I’m sure there is a good reason that I could not find.

ECDSA doesn’t have that.

Thanks.

Combinatorics challenge solved it Python

The easiest way to explain this problem is to show these two test cases:

assert solution('ABC') == ('A', 'B', 'C', 'AB', 'AC', 'BC', 'ABC')
assert solution('ABCD') ==  ('A', 'B', 'C', 'D', 'AB', 'AC', 'AD', 'BC', 'BD', 'CD', 'ABC', 'ABD', 'ACD', 'BCD', 'ABCD')

my solution is below:

def subsolution(lst, length):
    return (lst + (x) for x in·
            range(lst(-1)+1, length))

def solution(symbols):
    length = len(symbols)
    result = (((x) for x in range(length)))
    while True:
        subres = ()
        for x in result(-1):
            subres.extend(subsolution(x, length))
        if not subres:
            break
        result.append(subres)
    result = ( item for sublist in result
        for item in sublist
    )
    result = (
        ''.join(symbols(s) for s in el)
        for el in result
    )
    return result

programming challenge – C++, sort integers using knowledge of entire vector

I am solving the “Sort” problem on Kattis.

Mirko is a great code breaker. He knows any cipher in the world can be broken by frequency analysis. He has completely the wrong idea what frequency analysis is, however.
He intercepted an enemy message. The message consists of N
numbers, smaller than or equal to C.
Mirko belives freqency analysis consists of sorting this sequence so that more frequent numbers appear before less frequent ones.
Formally, the sequence must be sorted so that given any two numbers X
and Y, X appears before Y if the number of times X appears in the original sequence is larger than the number of time Y does. If the number of appearances is equal, the number whose value appears sooner in the input should appear sooner in the sorted sequence.
Help Mirko by creating a “frequency sorter”.
Input
First line of input contains two integers, N (1≤N≤1000), the length of the message, and C (1≤C≤1000000000), the number from the task description above.
The next line contains N positive integers smaller than or equal to C, the message itself.

Basically, the problem is as follows. Let xs be a nonempty vector of positive integers. There are only few integers in this vector, but they have a big range. (The maximum value c is given in the problem, but my code does not use the information.) Sort the integers according to the following criteria.

  1. For any two elements x and y of xs, if x occurs more often than y, then x appears first; if y appears more often, y appears first.
  2. If x and y appear equally often, then x occurs first if the very first occurrence of x is earlier than that of y.

I use a comparison sort (provided by the C++ runtime) with a smart comparator. This comparator knows the frequency and the index of the first appearance of every element. This information is not inherent to the integers. Rather, it depends entirely on their location within the vector. This contextual information is generated when a comparator is created for a given vector. Upon application on elements x and y, it returns true if x must appear before y.

I have used custom comparators before, but never have I used anything that contains state. In the disassembly with -Os I see many copy and move constructors called under sort(vector<unsigned> &). The code passes all tests, and it’s not slow.

But I wonder why the disassembly reveals so many copy and move calls, and whether this pattern of using heavy comparators is discouraged in C++. If this looks like a known pattern, I want to know its name. I appreciate general comments and insights.

#include <vector>
#include <set>
#include <map>
#include <algorithm>
#include <iostream>

typedef std::vector<unsigned> vector;

/// Comparison based on knowledge of the entire vector
struct compare {
    std::multiset<unsigned> bag;
    std::map<unsigned, size_t> indices;

    /// Extract frequency and initial index of every element.
    explicit compare(vector const &xs) {
        for (size_t i = 0u; i < xs.size(); ++i) {
            unsigned const x = xs(i);
            bag.insert(x);
            if (!indices.count(x)) {
                indices(x) = i;
            }
        }
    }

    /// True if `x` must go before `y`.
    ((nodiscard)) bool operator()(unsigned x, unsigned y) const {
        return bag.count(x) > bag.count(y)
               || (bag.count(x) == bag.count(y) && indices.at(x) < indices.at(y));
    }
};

static void sort(vector &v) {
    compare c(v);
    std::sort(v.begin(), v.end(), c);
}

int main() {
    vector v;
    {
        // Get `n` unsigned integers from console.
        // Unused: `c` (upper bound for integers)
        unsigned n, c;
        std::cin >> n >> c;
        v.reserve(n);
        while (n--) {
            unsigned x;
            std::cin >> x;
            v.push_back(x);
        }
    }
    // Sort according to the problem description
    sort(v);
    // Print all
    for (unsigned const x : v) {
        std::cout << x << ' ';
    }
    return 0;
}

Performance challenge: Box operations (HackerRank) (C, Python)

Recently I’ve been doing some challenges on HackerRank and came across this one. First, I tried with Python, and then C. Both of my codes failed due to timeout restrictions.

It would be very helpful, if someone can tell me what can be improved in (one of) my codes (performance-wise).

Thank you.

Challenge description:
Challenge description

C code:

int minBox(int *box, int l, int r){
    int min=box(l);
    for(int i = l+1; i<=r; i++)
        if(box(i) < min)
            min = box(i);
    
    return min;
}

int sumBox(int *box, int l, int r){
    int sum=0;
    for(int i = l; i<=r; i++)
        sum += box(i);

    return sum;
}

void operateOnBox(int *op, int *box){
    switch(op(0)){
        case 3:
            printf("%dn", minBox(box, op(1), op(2)));
            break;

        case 4:
            printf("%dn", sumBox(box, op(1), op(2)));
            break;

        case 1:
            for(int i = op(1); i <= op(2); i++)
                box(i) += op(3);

            break;

        case 2:
            for(int i = op(1); i <= op(2); i++)
                box(i) = (int) floor(box(i)/((float)op(3)));

            break;
    }
}

int main()
{

    int n, q, *box;
    scanf("%d %d", &n, &q);

    box = (int*) malloc(sizeof(int) * n);
    for(int i = 0; i<n; i++)
        scanf("%d", box+i);

    for(int i = 0; i<q; i++){
        int op(4);
        scanf("%d %d %d", op, op+1, op+2);

        if(op(0) == 1 || op(0) == 2)
            scanf("%d", op+3);
        
        operateOnBox(op, box);

    }

    return 0;
}

Python 3 code:

def operate(op, box):
    if op(0) == 3:
            print(min(box(op(1):op(2)+1)))
    elif op(0) == 4:
            print(sum(box(op(1):op(2)+1)))
    elif op(0) == 1:
            box(op(1):op(2)+1) = map(lambda x: x+op(3), box(op(1):op(2)+1))
    elif op(0) == 2:
            box(op(1):op(2)+1) = map(lambda x: math.floor(x/op(3)), box(op(1):op(2)+1))



if __name__ == '__main__':
    nq = input().split()

    n = int(nq(0))

    q = int(nq(1))

    box = list(map(int, input().rstrip().split()))

    for i in range(q):
        op = list(map(int, input().split()))
        operate(op, box)

What’s the biggest challenge you’ve ever faced in sales and marketing?

The hardest challenge for me has been trying to improve user experience to drive conversions on ecommerce websites. It takes a real specialist to look at the data analytics or other tools like Hotjar collects and turn it into any meaningful, or actionable insight. There’s no one size fits all for this sort of thing, so generic advice like keeping content above the fold or changing calls to action at points of conversion had been no use to myself or my teams. There was such a skills gap in the end that we’ve consulted with a number of CRO agencies. Conversion rate optimisation has been the sole driving force for change at so many businesses that struggled to grow online and I wholeheartedly recommend it to anyone looking to get ahead of the game.

 

Php challenge that requires some extra brain

I’m trying to do a small program that prints numbers from 1 to 100. In multiples of 3, the program should print “pizza”. In multiples of 5, the program should print “pancake”. And in multiples of both, it should print “pizzapancake”. Here’s the tricky part: You are not allowed to use more than ONE if, no else, no elseif no branching (such as switches), no ternary. Last thing, it should be done with PHP.

Here’s what I came up with

       <?php

    class printCondition
    {
        public $message = "";
        public $val = "";
        public function compare($mult, $num, $message){
            $result = $num/$mult;
            $this->val = $num;
            if(is_int($result) ){
                $this->val ="";
                $this->message .= $message;
            }
        }
    }
    for ($x=1; $x<=100 ; $x++ ){
        $obj = new printCondition();
        $obj->compare(3, $x, "pizza");
        $obj->compare(5, $x, "pancake");
        print $obj->message;
        print $obj->val;
        print "<br>";
    }



    ?>

It almost works, except because the number of multiples of 3 shows up:

introducir la descripción de la imagen aquí

If anyone has any advice on how can I accomplish my goal, I would be really thankful. I’m rather new to PHP and I don’t know about any library or workaround with classes and features that might work but If you do all advice is welcomed.

programming challenge – C: function to read a token from stdin

I recently started doing some competitive programming in C and one of my first requirements was a high-speed token reader (analogous to the java Scanner class’ next() function). Here’s the first prototype:

#define BUF_SIZE (1 << 10) // approx 2 KiB or 1024 chars

char* next_token() {
    char* buf = malloc(BUF_SIZE * sizeof(char));
    char cc;
    // consume leading whitespaces
    while (isspace(cc=getchar())) ;
    buf(0) = cc;
    int i=1;
    int nofs = 1;
    while (!isspace(cc=getchar())) {
        if (i >= BUF_SIZE*nofs) {
            // gracefully extend buffer size
            nofs++;
            buf = realloc(buf, BUF_SIZE*nofs*sizeof(char));
        }
        buf(i) = cc;
        i++;
    }
    // trim buffer
    buf = realloc(buf, (i+1)*sizeof(char));
    buf(i) = '';
    return buf;
}

Two questions I had with this code are:

  1. Is this fast enough? I think the major bottleneck lies with the realloc at the end, where I trim the length. If it’s not fast enough, please suggest some optimizations.
  2. Is this compliant with how C is generally written? I’m coming from Java and have little experience with C code. I write some embedded C but that’s closer to assembly than it is to this type of code.

Any further improvements are welcome.

python – Foobar Challenge- Bunny Prisoner Locating

Keeping track of Commander Lambda’s many bunny prisoners is starting to get tricky. You’ve been tasked with writing a program to match bunny prisoner IDs to cell locations.

The LAMBCHOP doomsday device takes up much of the interior of Commander Lambda’s space station, and as a result the prison blocks have an unusual layout. They are stacked in a triangular shape, and the bunny prisoners are given numerical IDs starting from the corner, as follows:

| 7

| 4 8

| 2 5 9

| 1 3 6 10

Each cell can be represented as points (x, y), with x being the distance from the vertical wall, and y being the height from the ground.

For example, the bunny prisoner at (1, 1) has ID 1, the bunny prisoner at (3, 2) has ID 9, and the bunny prisoner at (2,3) has ID 8. This pattern of numbering continues indefinitely (Commander Lambda has been taking a LOT of prisoners).

Write a function solution(x, y) which returns the prisoner ID of the bunny at location (x, y). Each value of x and y will be at least 1 and no greater than 100,000. Since the prisoner ID can be very large, return your solution as a string representation of the number.

The following is the code that I wrote that.


def solution(x,y):
    n=x+y-1
    s=(n*(n+1))//2
    res=s-y+1
    return str(res)

The question looked pretty straight forward but not even one test case passed when I tried this code.
The code seems to work just fine on other ide’s.
Is my solution correct or did I understand the question completely differently?

programming challenge – Sort Characters By Frequency Java

For context, I worked on the LeetCode May 2020 Challenge Week 3 Day 1. The challenge was described as this:

Given a string, sort it in decreasing order based on the frequency of
characters.

Example 1:

Input: "tree"

Output: "eert"

Explanation: 'e' appears twice while 'r' and 't' both appear once. So
'e' must appear before both 'r' and 't'. Therefore "eetr" is also a
valid answer.

Example 2:

Input: "cccaaa"

Output: "cccaaa"

Explanation: Both 'c' and 'a' appear three times, so "aaaccc" is also
a valid answer. Note that "cacaca" is incorrect, as the same
characters must be together.

Example 3:

Input: "Aabb"

Output: "bbAa"

Explanation: "bbaA" is also a valid answer, but "Aabb" is incorrect.
Note that 'A' and 'a' are treated as two different characters.

Anyways, I looked up some popular solutions. One was to get the frequency of each character and sort, and the other was the use a heap. I liked both of these solutions, but I wanted to make one where there was no sorting.

My solution involved an idea of an ArrayList of “tiers,” where the index of the tier represents the frequency. Each tier consists of an ArrayList containing the characters which the corresponding frequency. As letters increase in frequency, the higher frequency tier they move up. I also used a HashMap to keep track of which frequency tier each character was in. Upon finishing iterating through the whole string, I simply use a StringBuilder to append the letters starting at the bottom tier, reverse the StringBuilder, then return the String. I was hoping someone could give me pointers (ha, code pun) on optimizing/modifying this approach without including any kind of sorting. Below is the functional code:

public static String frequencySort(String s) {
        if (s.length() <= 1) return s;

        ArrayList<ArrayList<Character>> tieredFreq = new ArrayList<>(); // stores characters at their proper frequency "tier"
        HashMap<Character, Integer> tierOfChars = new HashMap<>(); // maps the characters to their current frequency tier
        tieredFreq.add(null); // tier 0

        for (char c : s.toCharArray()) {
            tierOfChars.put(c, tierOfChars.getOrDefault(c, 0) + 1); // add char or increment the tier of the character
            int i = tierOfChars.get(c); // i = tier of the character
            if (tieredFreq.size() <= i) tieredFreq.add(new ArrayList<>()); // if not enough tiers, add a new tier
            if (i > 1) tieredFreq.get(i - 1).remove(new Character(c)); // if c exists in previous tier, remove it
            tieredFreq.get(i).add(c); // add to new tier
        }

        StringBuilder result = new StringBuilder();
        for (int i = 1; i < tieredFreq.size(); i++) { // iterate through tiers
            ArrayList<Character> tier = tieredFreq.get(i); // get tier
            for (Character c : tier) { // for each char in tier, append to string a number of times equal to the tier
                for (int j = 0; j < i; j++) result.append(c);
            }
        }

        result.reverse(); // reverse, since result is currently in ascending order
        return result.toString();
    }

nginx – Http-01 challenge failed and connection refused

I just bought a new server and want to follow this for www.pretty-formula.com.

Here is the record I added to pretty-formula.com:
enter the image description here

On the server ufw status returned Status: inactive.

After putting pretty-formula.com In related files, I got this error:

root@iZj6ce932fiflob4gudnajZ:~/nginx-certbot# ./init-letsencrypt.sh 
Existing data found for pretty-formula.com. Continue and replace existing certificate? (y/N) y
### Creating dummy certificate for pretty-formula.com ...
Generating a RSA private key
......+++++
.........+++++
writing new private key to '/etc/letsencrypt/live/pretty-formula.com/privkey.pem'
-----
failed to resize tty, using default size

### Starting nginx ...
Recreating nginx-certbot_nginx_1 ... done

### Deleting dummy certificate for pretty-formula.com ...
failed to resize tty, using default size

### Requesting Let's Encrypt certificate for pretty-formula.com ...
Saving debug log to /var/log/letsencrypt/letsencrypt.log
Plugins selected: Authenticator webroot, Installer None
Obtaining a new certificate
Performing the following challenges:
http-01 challenge for pretty-formula.com
http-01 challenge for www.pretty-formula.com
Using the webroot path /var/www/certbot for all unmatched domains.
Waiting for verification...
Challenge failed for domain pretty-formula.com
Challenge failed for domain www.pretty-formula.com
http-01 challenge for pretty-formula.com
http-01 challenge for www.pretty-formula.com
Cleaning up challenges
Some challenges have failed.

IMPORTANT NOTES:
 - The following errors were reported by the server:

   Domain: pretty-formula.com
   Type:   connection
   Detail: Fetching
   http://pretty-formula.com/.well-known/acme-challenge/-yXehDZroR0bFBusF3tEM9Ja9tD1XEXDmAiDnWgP6u8:
   Connection refused

   Domain: www.pretty-formula.com
   Type:   connection
   Detail: Fetching
   http://www.pretty-formula.com/.well-known/acme-challenge/KbU_eUlIBexvG1zqN-UKB7lhdiIc7MEOYar1w-vlPNs:
   Connection refused

   To fix these errors, please make sure that your domain name was
   entered correctly and the DNS A/AAAA record(s) for that domain
   contain(s) the right IP address. Additionally, please check that
   your computer has a publicly routable IP address and that no
   firewalls are preventing the server from communicating with the
   client. If you're using the webroot plugin, you should also verify
   that you are serving files from the webroot path you provided.

### Reloading nginx ...
cannot exec in a stopped state: unknown

It is a new server and a new domain, I don't understand what it is blocking. Does anyone know how to investigate further?