Ok.
I will reply to my own post as I have already tested my solution and surprisingly… the mistake is in Twitter Documentation.
Documentation says:
Next, gather all of the parameters included in the request. There are two such locations for these additional parameters - the URL (as part of the querystring) and the request body.
Which is not true.
I removed body parameter from being taken into account while calculating the signature and everything works like a charm.
My suggestion is to not trust the documentation but experiment with Twitter REST API.